Множинне вирівнювання послідовностей (англ. multiple sequence alignment, MSA) — вирівнювання трьох і більше біологічних послідовностей, зазвичай білків, ДНК або РНК. У більшості випадків передбачається, що вхідний набір послідовностей має еволюційний зв'язок. Використовуючи множинне вирівнювання можна оцінити еволюційне походження послідовностей, провівши філогенетичний аналіз.

Візуалізація вирівнювання ілюструє мутаційні події як точкові мутації (зміна однієї амінокислоти або одного нуклеотиду) у вигляді спеціальних символів в одній колонці вирівнювання, а також гепи — їх вставки або делеції (зображуються знаком дефіса).

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

Зважаючи на більшу обчислювальну складність в порівнянні з парним вирівнюванням, множинне вирівнювання вимагає більш складні алгоритми. Багато програм використовують евристичні алгоритми, оскільки пошук глобального оптимального вирівнювання для багатьох послідовностей може займати тривалий час.

Динамічне програмування та обчислювальна складність Для безпосередньої побудови глобального оптимального вирівнювання використовується динамічне програмування. Для білкових послідовностей існує два набори параметрів: штраф за геп і матриця замін, що містить в собі ймовірності зіставлення пари амінокислотних залишків, які засновані на схожості їх хімічних властивостей і еволюційної ймовірності мутації. Для нуклеотидних послідовностей також використовується штраф за геп, але матриця замін набагато простіша, в ній враховуються тільки збіги нуклеотидів або неспівпадіння нуклеотидів (місматчі).

Для n окремих послідовностей наївний метод вимагає побудови n-мірного еквівалента матриці, яку використовують для парного вирівнювання. З ростом n простір пошуку зростає експоненціально. Таким чином, наївний алгоритм має обчислювальну складність O(Довжина послідовностейNпослідовностей). Пошук глобального оптимуму для n послідовностей відноситься до NP-повних завданньWang L., Jiang T. On the complexity of multiple sequence alignment. (англ.) // Journal of computational biology: a journal of computational molecular cell biology. — 1994. — Vol. 1, no. 4. — P. 337—348. — doi:10.1089/cmb.1994.1.337. — PMID 8790475.Just W. Computational complexity of multiple sequence alignment with SP-score. (англ.) // Journal of computational biology: a journal of computational molecular cell biology. — 2001. — Vol. 8, no. 6. — P. 615—623. — doi:10.1089/106652701753307511. — PMID 11747615.Elias I. Settling the intractability of multiple alignment. (англ.) // Journal of computational biology: a journal of computational molecular cell biology. — 2006. — Vol. 13, no. 7. — P. 1323—1339. — doi:10.1089/cmb.2006.13.1323. — PMID 17037961..

У 1989 році на основі алгоритму Каррільо — ЛіпманаCarrillo H., Lipman D. J. The Multiple Sequence Alignment Problem in Biology (англ.) // SIAM Journal of Applied Mathematics. — 1988. — Vol. 48, no. 5. — P. 1073—1082. — doi:10.1137/0148063.. Альтшуль представив практичний підхід, який використовував парні вирівнювання для обмеження n-мірного простору пошукуLipman D. J., Altschul S. F., Kececioglu J. D. A tool for multiple sequence alignment. (англ.) // Proceedings of the National Academy of Sciences of the United States of America. — 1989. — Vol. 86, no. 12. — P. 4412—4415. — PMID 2734293.. При такому підході динамічне програмування виконується на кожній парі послідовностей з вхідного набору і проводиться пошук лише ділянки, яка розташована поблизу n-мірного перетину цих шляхів. Програма оптимізує суму всіх пар символів в кожній позиції вирівнюванні.

Прогресивне вирівнювання Прогресивне вирівнювання застосовує евристичний алгоритм, розроблений Пауліеною Хогевег та Беном Геспером в 1984 роціHogeweg P., Hesper B. The alignment of sets of sequences and the construction of phyletic trees: an integrated method. (англ.) // Journal of molecular evolution. — 1984. — Vol. 20, no. 2. — P. 175—186. — PMID 6433036.. Всі методи прогресивного вирівнювання мають дві важливі стадії: побудова бінарного дерева (дороговказівне дерево), в якому листки є послідовностями, і побудова множинного вирівнювання шляхом додавання послідовностей до зростаючого вирівнювання згідно дороговказівного дерева. Саме дороговказівне дерево може бути побудованим методами кластеризації, такими як метод UPGMA і метод приєднання сусідівMount D. M. Bioinformatics: Sequence and Genome Analysis 2nd ed. (англ.) // Cold Spring Harbor. — 2004..

Прогресивне вирівнювання не гарантує отримання оптимального глобального вирівнювання. Проблема полягає в тому, що помилки, отримані на будь-якій стадії зростаючого множинного вирівнювання, доходять до кінцевого вирівнювання. Крім того, вирівнювання може бути особливо поганим у випадку сильно віддалених одна від одної послідовностей. Більшість сучасних прогресивних методів мають змінену функцію обчислення ваги з вторинною ваговою функцією, яка присвоює коефіцієнти для окремих елементів набору даних у вигляді нелінійної моди заснованої на філогенетичній відстані від найближчих сусідів. Методи прогресивного вирівнювання досить ефективні, щоб застосовувати їх для великого числа (100—1000) послідовностей. Найпопулярніший метод прогресивного вирівнювання належить до сімейства ClustalHiggins D. G., Sharp P. M. CLUSTAL: a package for performing multiple sequence alignment on a microcomputer. (англ.) // Gene. — 1988. — Vol. 73, no. 1. — P. 237—244. — PMID 3243435., зокрема, варіант ClustalWThompson J. D., Higgins D. G., Gibson T. J. CLUSTAL W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting, position-specific gap penalties and weight matrix choice. (англ.) // Nucleic acids research. — 1994. — Vol. 22, no. 22. — P. 4673—4680. — PMID 7984417., доступ до якого можна отримати через такі портали як GenomeNet, EBI, EMBNet. ClustalW активно використовується для побудови філогенетичних дерев, незважаючи на попередження автора, що неперевірені вручну вирівнювання не повинні використовуватися ні при побудові дерев, ні в якості вхідних даних для передбачення структури білків. Поточна версія Clustal — Clustal Omega, яка працює на основі дороговказівних дерев і HMM профіль-профільних методів для білкових вирівнювань.

Схема методу прогресивного множинного вирівнювання реалізованого в програмі Clustal Omega:

1. На самому початку програма будує всі парні вирівнювання аналізованих послідовностей;

2. Відповідно до парних вирівнювань отримують матрицю еволюційних дистанцій;

3. Формується кластерна діаграма (філогенетичного дерево), що побудована відповідно до матриці еволюційних дистанцій;

4. Відповідно до філогенетичного дерева програма будує множинне вирівнювання з використанням алгоритму глобального вирівнювання методом динамічного програмування.

Після проведення парного (глобального) вирівнювання кожної послідовності зі всіма, на наступному етапі розраховується дистанція між вирівняними послідовностями. Найпростіший спосіб визначення генетичної відстані базується на підрахунку позицій в вирівнюванні де спостерігаються заміни. Ультраметричне філогенетичне дерево дозволяє зробити висновки про еволюційне походження даної групи послідовностей та відібрати пари, для яких буде проведено так зване довирівнювання.

Існують різні інструменти для побудови прогресивного вирівнювання послідовностей ДНК. Один з них — MAFFT (англ. Multiple Alignment using Fast Fourier Transform).

Інший поширений метод прогресивного вирівнювання, T-Coffee, повільніший, ніж Clustal і його похідні, але найчастіше дає точніші вирівнювання для віддалено пов'язаних послідовностей. T-Coffee будує бібліотеку парних вирівнювань, яку потім використовує для побудови множинного вирівнюванняNotredame C., Higgins D. G., Heringa J. T-Coffee: A novel method for fast and accurate multiple sequence alignment. (англ.) // Journal of molecular biology. — 2000. — Vol. 302, no. 1. — P. 205—217. — doi:10.1006/jmbi.2000.4042. — PMID 10964570..

Ітеративні методи Набір методів для побудови множинних вирівнювань, в яких відбувається зниження помилок, отриманих прогресивними методами, класифікують як «ітеративні». Вони працюють аналогічно прогресивним методам, але при цьому неодноразово перебудовують вихідні вирівнювання при додаванні нових послідовностей. Прогресивні методи сильно залежать від якості початкових вирівнювань, оскільки вони в незмінному вигляді, а отже і з помилками, потраплять в кінцевий результат. Іншими словами, якщо послідовність вже потрапила в вирівнювання, її подальше становище не зміниться. Таке наближення покращує ефективність, але негативно позначається на точності результату. На відміну від прогресивних методів, ітеративні методи можуть повертатися до спершу порахованим парним вирівнювання і підвирівнюванням, що містять підмножини послідовностей із запиту, і таким чином оптимізувати загальну цільову функцію і підвищувати якість.

Існує велика кількість різноманітних ітеративних методів. Наприклад, PRRN/PRRP використовує алгоритм сходження до вершини для оптимізації ваги множинного вирівнюванняGotoh O. Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments. (англ.) // Journal of molecular biology. — 1996. — Vol. 264, no. 4. — P. 823—838. — doi:10.1006/jmbi.1996.0679. — PMID 8980688. і ітеративно коригує ваги вирівнювання і ділянки з великою кількістю гепів. PRRP працює ефективніше, коли покращує вирівнювання, попередньо побудоване швидким методом.

Ще одна ітеративна програма, DIALIGN, використовує оригінальний підхід, вона проводить локальні вирівнювання підсегментів або мотивів послідовностей без введення штрафу за гепBrudno M., Chapman M., Göttgens B., Batzoglou S., Morgenstern B. Fast and sensitive multiple alignment of large genomic sequences. (англ.) // BMC bioinformatics. — 2003. — Vol. 4. — P. 66. — doi:10.1186/1471-2105-4-66. — PMID 14693042.. Вирівнювання окремих мотивів реалізується в матричному вигляді, подібному до діаграмою з точками (dot-plot) в парному вирівнюванні. В програмі CHAOS/DIALIGN використовується альтернативний метод, який використовує швидкі локальні вирівнювання в якості точок прив'язки для більш повільної процедури побудови глобального вирівнювання.

Третій популярний ітераційний метод називається MUSCLE. Він дає кращий результат ніж прогресивні методи, оскільки використовує більш точні відстані для оцінки зв'язку двох послідовностей. Цей метод реалізує оновлення відстаней між ітераціями (хоча в первісному вигляді MUSCLE містив тільки 2—3 ітерації)Edgar R. C. MUSCLE: multiple sequence alignment with high accuracy and high throughput. (англ.) // Nucleic acids research. — 2004. — Vol. 32, no. 5. — P. 1792—1797. — doi:10.1093/nar/gkh340. — PMID 15034147..

Консенсусні методи Консенсусні методи намагаються вибрати оптимальне множинне вирівнювання з різних множинних вирівнювань одного і того ж набору вхідних даних. Існують два найбільш поширених консенсусних методів: M-COFFEE та MergeAlignCollingridge P. W., Kelly S. MergeAlign: improving multiple sequence alignment performance by dynamic reconstruction of consensus multiple sequence alignments. (англ.) // BMC bioinformatics. — 2012. — Vol. 13. — P. 117. — doi:10.1186/1471-2105-13-117. — PMID 22646090.. M-COFFEE використовує множинні вирівнювання, що генеруються 7 різними методами для отримання консенсусних вирівнювань. MergeAlign здатний генерувати консенсусні вирівнювання з будь-якого числа вхідних вирівнювань, отриманих з різних моделей еволюції послідовності і методів побудови. Опція за замовчуванням для MergeAlign — виведення консенсусного вирівнювання, використовуючи вирівнювання, отримані з 91 різних моделей еволюції білкової послідовності.

Приховані марковські моделі Див. також: Прихована марковська модель