Как вычислить множественное выравнивание последовательностей для текстовых строк
Я пишу программу, которая должна вычислить множественное выравнивание последовательности набора строк. Я думал об этом в 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 является зрелым инструментом для выравнивания биологической последовательности, режим выравнивания текста находится на стадии разработки, с планами на будущее, включая предоставление разрешенных пользователем матриц подсчета очков. Более подробную информацию вы можете найти в документации.