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

Question

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

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

Спасибо!

Answer 1

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

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

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

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

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

Answer 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()

Answer 3

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

mafft --text input_text.fa > output_alignment.fa

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

Answer 4

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