Множинне вирівнювання послідовностей

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

Для n окремих послідовностей наївний метод вимагає побудови n-мірного еквівалента матриці, яку використовують для парного вирівнювання. З ростом n простір пошуку зростає експоненціально. Таким чином, наївний алгоритм має обчислювальну складність O(Довжина послідовностей^{Nпослідовностей}). Пошук глобального оптимуму для n послідовностей відноситься до NP-повних завданнь[2][3][4].

У 1989 році на основі алгоритму Каррільо – Ліпмана[5]. Альтшуль представив практичний підхід, який використовував парні вирівнювання для обмеження n-мірного простору пошуку[6]. При такому підході динамічне програмування виконується на кожній парі послідовностей з вхідного набору і проводиться пошук лише ділянки, яка розташована поблизу n-мірного перетину цих шляхів. Програма оптимізує суму всіх пар символів в кожній позиції вирівнюванні.

Прогресивне вирівнювання застосовує евристичний алгоритм, розроблений Пауліеною Хогевег та Беном Геспером в 1984 році[7]. Всі методи прогресивного вирівнювання мають дві важливі стадії: побудова бінарного дерева (дороговказівне дерево), в якому листки є послідовностями, і побудова множинного вирівнювання шляхом додавання послідовностей до зростаючого вирівнювання згідно дороговказівного дерева. Саме дороговказівне дерево може бути побудованим методами кластеризації, такими як метод UPGMA і метод приєднання сусідів[8].

Прогресивне вирівнювання не гарантує отримання оптимального глобального вирівнювання. Проблема полягає в тому, що помилки, отримані на будь-якій стадії зростаючого множинного вирівнювання, доходять до кінцевого вирівнювання. Крім того, вирівнювання може бути особливо поганим у випадку сильно віддалених одна від одної послідовностей. Більшість сучасних прогресивних методів мають змінену функцію обчислення ваги з вторинною ваговою функцією, яка присвоює коефіцієнти для окремих елементів набору даних у вигляді нелінійної моди заснованої на філогенетичній відстані від найближчих сусідів[8]. Методи прогресивного вирівнювання досить ефективні, щоб застосовувати їх для великого числа (100—1000) послідовностей. Найпопулярніший метод прогресивного вирівнювання належить до сімейства Clustal[9], зокрема, варіант ClustalW[10], доступ до якого можна отримати через такі портали як GenomeNet, EBI, EMBNet. ClustalW активно використовується для побудови філогенетичних дерев, незважаючи на попередження автора, що неперевірені вручну вирівнювання не повинні використовуватися ні при побудові дерев, ні в якості вхідних даних для передбачення структури білків. Поточна версія Clustal — Clustal Omega, яка працює на основі дороговказівних дерев і HMM профіль-профільних методів для білкових вирівнювань.

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

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

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

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

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

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

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

Інший поширений метод прогресивного вирівнювання, T-Coffee[13], повільніший, ніж Clustal і його похідні, але найчастіше дає точніші вирівнювання для віддалено пов'язаних послідовностей. T-Coffee будує бібліотеку парних вирівнювань, яку потім використовує для побудови множинного вирівнювання[14].

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

Існує велика кількість різноманітних ітеративних методів. Наприклад, PRRN/PRRP[15] використовує алгоритм сходження до вершини для оптимізації ваги множинного вирівнювання[16] і ітеративно коригує ваги вирівнювання і ділянки з великою кількістю гепів[8]. PRRP працює ефективніше, коли покращує вирівнювання, попередньо побудоване швидким методом[8].

Ще одна ітеративна програма, DIALIGN, використовує оригінальний підхід, вона проводить локальні вирівнювання підсегментів або мотивів послідовностей без введення штрафу за геп[17]. Вирівнювання окремих мотивів реалізується в матричному вигляді, подібному до діаграмою з точками (dot-plot) в парному вирівнюванні. В програмі CHAOS/DIALIGN[18] використовується альтернативний метод, який використовує швидкі локальні вирівнювання в якості точок прив’язки для більш повільної процедури побудови глобального вирівнювання[17].

Третій популярний ітераційний метод називається MUSCLE[19]. Він дає кращий результат ніж прогресивні методи, оскільки використовує більш точні відстані для оцінки зв'язку двох послідовностей. Цей метод реалізує оновлення відстаней між ітераціями (хоча в первісному вигляді MUSCLE містив тільки 2—3 ітерації)[20].

Консенсусні методи намагаються вибрати оптимальне множинне вирівнювання з різних множинних вирівнювань одного і того ж набору вхідних даних. Існують два найбільш поширених консенсусних методів: M-COFFEE[21] та MergeAlign[22][23]. M-COFFEE використовує множинні вирівнювання, що генеруються 7 різними методами для отримання консенсусних вирівнювань. MergeAlign здатний генерувати консенсусні вирівнювання з будь-якого числа вхідних вирівнювань, отриманих з різних моделей еволюції послідовності і методів побудови. Опція за замовчуванням для MergeAlign — виведення консенсусного вирівнювання, використовуючи вирівнювання, отримані з 91 різних моделей еволюції білкової послідовності.

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

У біоінформатиці метод прихованих марковских моделей (Hidden Markov model, HMM) служить для опису тонких відмінностей, що існують між сімействами гомологічних послідовностей. Метод HMM ефективний і при прогнозі шляхів згортання білків. Цей метод повністю базується на аналізі послідовностей (тобто не використовує структурну інформацію).

Програми, засновані на HMM, представляють множинне вирівнювання у вигляді спрямованого ациклічного графа, відомого як граф часткового порядку, який складається з серій вузлів, які є можливими станами в колонках вирівнювання. В такому разі абсолютно консервативна колонка (тобто послідовності, які при множинному вирівнюванні мають в даній позиції певний символ) кодується як один вузол з безліччю вихідних з'єднань з символами, можливими в наступній позиції вирівнювання. У термінах стандартної прихованої марковської моделі такі окремі колонки вирівнювання є станами, спостерігаються, а «приховані» стани являють собою передбачувану предкову послідовність, від якої послідовності вхідного набору могли еволюцінувати[8].

Програми, в яких реалізований метод НММ для аналізу біологічних послідовностей, можуть робити наступне[1]:

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

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

3. Вирівнювання додаткових послідовностей. Імовірність проходження будь-якого маршруту в даній НММ, тобто ймовірність отримання саме даного набору станів, може бути розрахована з індивідуальних ймовірностей переходів "стан-за-станом" (state-by-state).

Незважаючи на те, що HMM-методи більш складні, ніж популярні прогресивні методи, існує кілька програм для отримання вирівнювань, наприклад, POA[24], а також схожий, але більш узагальнений метод в пакетах SAM[25][26] і HMMER[27][28]. HHsearch, заснований на парному порівнянні HMMs, використовується для пошуку віддалено пов'язаних послідовностей. Сервер HHsearch (HHpred) був найшвидшим з 10 кращих автоматичних серверів, ввикористаних для передбачення структур білків CASP7 і CASP8[29].

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

Перший метод, заснований на аналізі філогенії, був розроблений Лойтіноджом і Голдманом в 2005 році[30]. У 2008 році ті ж автори випустили відповідне програмне забезпечення — PRANK[31][32]. PRANK удосконалює вирівнювання, коли є вставки. Тим не менш, він працює повільніше, ніж прогресивні і / або ітеративні методи[33], які були розроблені за кілька років до того.

У 2012 році з'явилися два нових методи, заснованих на філогенетичному аналізі. Перший, під назвою PAGAN, був розроблений командою PRANK, а другий, названий ProGraphMSA, був розроблений Жалковським[34]. Їх програмне забезпечення було розроблено незалежно, але вони мають загальні риси: обидва використовують алгоритми на графах для поліпшення розпізнавання негомологічних регіонів, при цьому вони швидші за метод PRANK.

Пошук мотивів або, інакше, аналіз профілів - це метод пошуку локалізації мотиву в глобальному множинному вирівнюванні як засіб отримання кращого MSA і середньовагової матриці з метою використання її для пошуку інших послідовностей з подібними мотивами. Було розроблено велику кількість методів для визначення мотивів, але всі вони ґрунтуються на виявленні коротких висококонсервативних патернів в більшому по довжині вирівнювання патерні і конструюванні матриці, подібної до матриці замін. Ця матриця відображає нуклеотідний або амінокислотний склад для кожної позиції в передбачуваному мотиві. Потім вирівнювання може бути уточнено за допомогою цих матриць. У стандартному аналізі профілів ця матриця включає в себе запис як для кожного можливого символу, так і для гепа[8]. На противагу цьому, статистичний алгоритм пошуку патернів спочатку шукає мотиви, а потім використовує знайдені мотиви для побудови множинного вирівнювання. У багатьох випадках, коли вхідний набір послідовностей містить невелику кількість послідовностей або  виключно високо споріднені  послідовності, додаються псевдокаунти для нормалізації розподілу, відображеного у ваговій матриці. Зокрема, це допомагає уникати нулів в матриці ймовірностей, щоб не отримати значення нескінченності в позиційній ваговій матриці.

Аналіз блоків — це метод пошуку мотивів в ділянках вирівнювання без гепів. Блоки можуть бути згенеровані з множинного вирівнювання або отримані з невирівняних послідовностей шляхом попереднього розрахунку множини загальних мотивів відомих сімейств генів[35]. Оцінка блоків зазвичай ґрунтується на просторі символів з високою частотою наявності в блоках, а не на обчисленні в явному вигляді матриць замін. Сервер BLOCKS надає альтернативний метод для локалізації таких мотивів в невирівняні послідовності.

Статистичне зіставлення патернів здійснюється за допомогою алгоритму максимізації очікування і семплювання за Гіббсом. Для пошуку мотивів найбільш часто використовується сервер MEME[36], що використовує алгоритм максимізації очікування і метод прихованих марковських моделей, а також MEME/MAST[37], який додатково використовує алгоритм MAST[38].