Блог

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

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

Спасибо!

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

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

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

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

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

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

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

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

 mafft --text input_text.fa > output_alignment.fa
  

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

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