Каков алгоритм, лежащий в основе выравнивания пар 2 в BioPython?

#algorithm #nlp #biopython

Вопрос:

Пакет BioPython позволяет вычислять попарно локальное или глобальное выравнивание с помощью различных функций (align.globalxx, align.localxx, …).

Однако я нигде не нашел алгоритма, на котором основано это выравнивание. В коде (источник, документ) говорится: «Выравнивание попарной последовательности с использованием алгоритма динамического программирования», и это все.

Есть ли документ, на котором основана эта реализация?
Использует ли он «стандартный алгоритм», и если да, то как он называется?

Редактировать: Это вопрос больше для цитирования, чем для понимания.

1. Ссылка, которую вы даете, относится к .py исходному файлу, а не к документации.

2. Вот документация: biopython.org/docs/1.75/api/Bio.pairwise2.html

3. И вот список документов, перечисленных здесь: biopython.org/wiki/Documentation

4. @MattDMo Если я процитирую это в научной статье, мне нужно будет сказать: «мы использовали реализацию алгоритма biopython BLA, подробно описанную в статье BLI», и на данный момент у меня нет ни BLA, ни BLI.

5. Я предполагаю, что это зависит от научной области — обычно это один из таких случаев использования, когда мне действительно нужно имя алгоритма, иначе меня спросят, почему я не использовал stg более стандартно.

Ответ №1:

Строка документа частной функции в коде указывает, что «Это реализация алгоритма динамического программирования Нидлмана-Вунша, модифицированного Gotoh, реализующего штрафы за аффинные пробелы». (л. 761 этого кода).

1. в будущем рассмотрите возможность использования более быстрых и гибких Bio.Align алгоритмов, где алгоритмы включают Нидлмана-Вунша, Смита-Уотермана, Гото, Уотермана-Смита-Бейера