Как вычислить множественное выравнивание последовательностей для текстовых строк

Я пишу программу, которая должна вычислить множественное выравнивание последовательности набора строк. Я думал об этом в Python, но я мог бы использовать внешнюю часть программного обеспечения или другой язык, если это было бы более практичным. Данные не особенно большие, у меня нет сильных требований к производительности, и я могу терпеть приближения (т.е. Мне просто нужно найти достаточно хорошее выравнивание). Единственная проблема заключается в том, что строки являются регулярными строками (т.е. Строки UTF-8, потенциально с новыми строками, которые следует рассматривать как обычный символ); они не являются последовательностями ДНК или белковыми последовательностями.

Я могу найти множество инструментов и информации для обычных случаев в биоинформатике с конкретными сложными форматами файлов и множеством функций, которые мне не нужны, но нетрудно найти программное обеспечение, библиотеки или пример кода для простого случая строк. Возможно, я мог бы переопределить любой из многих алгоритмов для этой проблемы или закодировать свою строку как ДНК, но должен быть лучший способ. Вы знаете какие-либо решения?

Спасибо!

Ответ 1

Самый простой способ выровнять несколько последовательностей - сделать несколько парных выравниваний.

Сначала получите парные оценки подобия для каждой пары и сохраните эти оценки. Это самая дорогая часть процесса. Выберите пару, которая имеет лучший счет сходства и сделайте это выравнивание. Теперь выберите последовательность, которая лучше всего соответствует одной из последовательностей в наборе выровненных последовательностей, и выровняйте ее с выровненным набором на основе этого парного выравнивания. Повторяйте, пока не появятся все последовательности.

При выравнивании последовательности выровненные последовательности (на основе парное выравнивание), когда вы вставляете разрыв в последовательности, которая уже находится в набор, вы вставляете пробелы в одном и том же место во всех последовательностях в выровненном набор.

Lafrasu предложил алгоритм SequneceMatcher() использовать для парного выравнивания строк UTF-8. То, что я описал, дает вам довольно безболезненный, разумно приемлемый способ расширить его до нескольких последовательностей.

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

Ответ 2

Вы ищете что-то быстрое и грязное, как в следующем?

from difflib import SequenceMatcher

a = "dsa jld lal"
b = "dsajld kll"
c = "dsc jle kal"
d = "dsd jlekal"

ss = [a,b,c,d]

s = SequenceMatcher()

for i in range(len(ss)):
    x = ss[i]
    s.set_seq1(x)
    for j in range(i+1,len(ss)):

        y = ss[j]
        s.set_seq2(y)

        print
        print s.ratio()
        print s.get_matching_blocks()

Ответ 3

Недавно я написал python script, который запускает алгоритм Смита-Уотермана (это то, что используется для создания локализованных локальных последовательностей последовательности для ДНК или последовательности белка). Это почти наверняка не самая быстрая реализация, поскольку я не оптимизировал ее для скорости вообще (не мое узкое место на данный момент), но она работает и не заботится об идентичности каждого символа в строках. Я мог бы опубликовать его здесь или отправить вам по электронной почте файлы, если это то, что вы ищете.

Ответ 4

MAFFT версия 7.120+ поддерживает несколько выравниваний текста. Ввод похож на формат FASTA, но с текстом LATIN1 вместо последовательностей и вывода выровнен формат FASTA. После установки его легко запустить:

mafft --text input_text.fa > output_alignment.fa

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