Обратный путь Хэмминга

Ответ 1

def mutations(word, hamming_distance, charset='ATCG'):
    for indices in itertools.combinations(range(len(word)), hamming_distance):
        for replacements in itertools.product(charset, repeat=hamming_distance):
            mutation = list(word)
            for index, replacement in zip(indices, replacements):
                mutation[index] = replacement
            yield "".join(mutation)

Эта функция генерирует все мутации слова с расстоянием от хамминга, которое меньше или равно заданному числу. Он относительно эффективен и не проверяет недопустимые слова. Однако допустимые мутации могут появляться более одного раза. Используйте set, если вы хотите, чтобы каждый элемент был уникальным.

Ответ 2

Пусть заданное расстояние Хэмминга - D и w - подстрока "слова". Из w вы можете сгенерировать все слова с расстоянием ≤D с помощью ограниченного по глубине поиска по глубине:

def dfs(w, D):
    seen = set([w])      # keep track of what we already generated
    stack = [(w, 0)]

    while stack:
        x, d = stack.pop()
        yield x

        if d == D:
            continue

        # generate all mutations at Hamming distance 1
        for i in xrange(len(x)):
            for c in set("ACGT") - set(x[i])
                 y = x[:i] + c + x[i+1:]
                 if y not in seen:
                     seen.add(y)
                     stack.append((y, d + 1))

(Это ни в коем случае не будет быстрым, но может служить вдохновением.)

Ответ 3

Если я правильно понимаю вашу проблему, вы хотите определить наивысшие оценки k-mers в геноме G. Оценка k-mer - это количество раз, которое оно появляется в геноме, а также количество раз, когда в геноме появляется любой k-mer с расстоянием Хэмминга менее m. Обратите внимание, что это предполагает, что вас интересуют только k-mers, которые появляются в вашем геноме (как указано @j_random_hacker).

Это можно решить четырьмя основными шагами:

• Определите все k-mers в геноме G.
• Подсчитайте количество раз, когда каждый k-mer появляется в G.
• Для каждой пары (K1, K2) k-mers увеличивайте счетчик как для K1, так и для K2, если их расстояние Хэмминга меньше m.
• Найдите max k-mer и его счет.

Здесь пример кода Python:

from itertools import combinations
from collections import Counter

# Hamming distance function
def hamming_distance(s, t):
    if len(s) != len(t):
        raise ValueError("Hamming distance is undefined for sequences of different lengths.")
    return sum( s[i] != t[i] for i in range(len(s)) )

# Main function
# - k is for k-mer
# - m is max hamming distance
def hamming_kmer(genome, k, m):
    # Enumerate all k-mers
    kmers = [ genome[i:i+k] for i in range(len(genome)-k + 1) ]

    # Compute initial counts
    initcount  = Counter(kmers)
    kmer2count = dict(initcount)

    # Compare all pairs of k-mers
    for kmer1, kmer2 in combinations(set(kmers), 2):
        # Check if the hamming distance is small enough
        if hamming_distance(kmer1, kmer2) <= m:
            # Increase the count by the number of times the other
            # k-mer appeared originally
            kmer2count[kmer1] += initcount[kmer2]
            kmer2count[kmer2] += initcount[kmer1]

    return kmer2count


# Count the occurrences of each mismatched k-mer
genome = 'ACGTTGCATGTCGCATGATGCATGAGAGCT'
kmer2count = hamming_kmer(genome, 4, 1)

# Print the max k-mer and its count
print max(kmer2count.items(), key=lambda (k,v ): v )
# Output => ('ATGC', 5)

Ответ 4

Здесь я думаю, что проблема, которую вы пытаетесь решить, такова: у вас есть "геном" длины n, и вы хотите найти k-mer, который наиболее часто появляется в этом геноме, где "примерно появляется" "появляется с расстоянием Хемминга <= d. Этот k-mer действительно не должен появляться точно в любом месте генома (например, для генома ACCA, k = 3 и d = 1, лучший k-mer - это CCC, появляющийся дважды).

Если вы генерируете все k-mers расстояния Хэмминга <= d из некоторого k-mer в строке и затем выполняете поиск каждого в строке, как вы, кажется, сейчас делаете, то вы добавляете ненужный O (n) к времени поиска (если вы не будете искать их все одновременно, используя алгоритм Aho-Corasick, но это переполнение здесь).

Вы можете добиться большего, пройдя через геном, и в каждой позиции i, создавая набор всех k-mers, которые находятся на расстоянии <= d от k-mer, начиная с позиции я в геноме, и увеличивая счетчик для каждого.

Ответ 5

def generate_permutations_close_to(initial = "GACT",charset="GACT"):
    for i,c in enumerate(initial):
         for x in charset:
             yield initial[:i] + x + inital[i+1:]

будет генерировать перестановки с расстоянием от 1 (он также будет повторять повторяющиеся повторы)

чтобы получить набор из всех в пределах 2... затем вызовите это с каждым из первых решений в качестве исходных догадок

Ответ 6

Здесь есть правильные ответы, которые в значительной степени используют питон с магическими функциями, которые делают почти все для вас. Я попытаюсь объяснить вещи математикой и алгоритмами, чтобы вы могли применить ее к любому желаемому языку.

Итак, у вас есть алфавит {a1, a2, ... a_a} (мощность a) в вашем случае {'A', 'C', 'G', 'T'}, а мощность равна 4. У вас есть строка длины k, и вы хотите сгенерировать все строки, чьи помехи расстояние меньше или равно d.

Прежде всего, сколько из них у вас есть? Ответ не зависит от выбранной вами строки. Если вы выбрали укус, у вас будет строка C(d, k)(a-1)^d, у которой есть расстояние от помехи d от вашей строки. Таким образом, общее количество строк:

Он растет экспоненциально в терминах почти каждого параметра, поэтому у вас не будет какого-либо быстрого алгоритма для поиска всех слов.

Итак, как бы вы вывели алгоритм, который будет генерировать все строки? Обратите внимание на то, что легко создать строку, которая не более чем на одном расстоянии от вашего wold. Вам просто нужно перебрать все символы в строке, и для каждого символа попробуйте каждую букву в алфавите. Как вы увидите, некоторые из слов будут одинаковыми.

Теперь, чтобы сгенерировать все строки, которые являются двумя расстояниями от хамминга от вашей строки, вы можете применить ту же функцию, которая генерирует одно слово hamming distance для каждого слова в предыдущей итерации.

Итак, вот псевдокод:

function generateAllHamming(str string, distance int): 
    alphabet = ['A', ...]// array of letters in your alphabet
    results = {} // empty set that will store all the results
    prev_strings = {str} // set that have strings from the previous iterations
    // sets are used to get rid of duplicates

    if distance > len(str){ distance = len(str)} // you will not get any new strings if the distance is bigger than length of the string. It will be the same all possible strings.

    for d = 0; d < distance; d++ {
        for one_string in prev_strings {
            for pos = 0; pos < len(one_string); pos++ {
                for char in alphabet {
                    new_str = substitute_char_at_pos(one_string, char, pos)
                    add new_str to set results 
                }
            }
        }

        populate prev_strings with elements from results
    }

    return your results
}