Биологические последовательности сравниваются для определения их функций и эволюционной истории. Этот процесс основан на концепции гомологии, которая подразумевает наличие общих предков и сходство биологических функций. Определение взаимосвязей между геномами помогает ученым понять эволюционные изменения, такие как мутации, дупликации и инверсии. Для автоматизации этого процесса были разработаны различные алгоритмы, каждый из которых имеет свои цели и уровень точности.
Для определения того, насколько тесно связаны две биологические последовательности, используется несколько математических методов. Идентичность последовательности измеряет точный процент совпадения выровненных остатков, в то время как расстояние Хэмминга подсчитывает количество несоответствий между последовательностями одинаковой длины. Для более сложных сценариев, включающих вставки или удаления, расстояние Левенштейна вычисляет минимальное количество односимвольных операций, необходимых для преобразования одной последовательности в другую. Эти показатели обеспечивают фундаментальную систему оценки для алгоритмов выравнивания.
Эффективная автоматизация выравнивания последовательности требует динамического программирования для решения крупномасштабных задач путем разбиения их на более мелкие, повторяющиеся подзадачи. Задача визуализируется с помощью манхэттенского графа, где узлы представляют собой остатки, а ребра - операции сопоставления, несовпадения или разрыва. Для глобального выравнивания, при котором обрабатывается вся длина последовательности, основным инструментом является алгоритм Нидлмана-Вунша. Этот метод обеспечивает получение глобального максимального балла, хотя его вычислительная сложность пропорциональна произведению длин последовательностей.
Локальное выравнивание направлено на поиск наиболее похожих подразделов в последовательностях, что особенно полезно при сравнении последовательностей разной длины или поиске общих доменов. Алгоритм Смита-Уотермана изменяет логику глобального выравнивания, вводя минимальный нулевой балл, предотвращающий влияние отрицательных значений на благоприятные локальные совпадения. Такой подход позволяет идентифицировать гомологичные участки даже в отдаленно родственных последовательностях. Современные вариации, такие как полуглобальные и перекрывающиеся выравнивания, обеспечивают дополнительную гибкость для конкретных исследовательских нужд.
Для повышения точности выравнивания используются оценочные матрицы, отражающие исторические эволюционные закономерности. Сравнение нуклеотидов часто учитывает переходы и трансверсии, поскольку переходы между химически сходными основаниями происходят чаще, чем трансверсии. Что касается белков, то матрицы PAM и BLOSUM являются отраслевыми стандартами и дают оценки, основанные на вероятности аминокислотных замен, встречающихся в природе. Понимание этих матриц имеет решающее значение для выбора правильных параметров при использовании инструментов поиска, таких как BLAST, или для управления данными о последовательности FASTA.