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

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

… це те саме, що парне, тільки послідовностей скільки завгодно

Навіщо будують множинні вирівнювання?

дозволяє знайти спільне

мотиви, патерни, профілі

пошук активного центру

передбачення3D-структури

дозволяє оцінити еволюційні відносини

Реконструкція еволюції

Побудова множинних вирівнювань – необхідний етап вирішення багатьох завдань молекулярної біології.

Червоним виділено консервативні (однакові в усіх) залишки; жовтим – на 80% консервативні (однакові майже у всіх) залишки

Червоним виділено консервативні та функціонально консервативні залишки.

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

1. Будь-яке множинне вирівнювання породжує набір парних вирівнювань
2. Не будь-який набір парних вирівнювань можна просто "скласти" у множинне вирівнювання.

Біологічна задача - поставити один під одним гомологічні позиції

​

Математична задача знайти спосіб кількісного порівняння якості вирівнювань.

​

Програмування - створення ефективного алгоритму та його реалізація

Методи прогресивного вирівнювання

Методи побудови множинного вирівнювання шляхом послідовного поєднання попарних вирівнювань

• Як правило, спочатку будується наближене дерево філогенезу

• За допомогою дерева вибирається порядок побудови попарних вирівнювань

• Далі послідовності додаються по черзі до головного вирівнювання, або вирівнювання (профілі) вирівнюються один з одним

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

​

Що корисного?

• Виявлення віддаленої гомології
• Виявлення консервативних залишків та мотивів
• Побудова філогенетичних дерев

​

Алгоритми:

-Динамічне програмування

• Побудова профілів
• Прогресивне вирівнювання
• Ітеративні методи
• Приховані марківські моделі

Прогресивне вирівнювання. Clustal

Clustal (1988) виконує поступове вирівнювання нових послідовностей, починаючи з найбільш <еволюційно> близьких, орієнтуючись на попередньо побудоване на підставі парних вирівнювань філогенетичне дерево.

Алгоритм:

1. Експрес-оцінка вирівнювання двох послідовностей обчислюється як число збігаються залишків у словах довжини K (K = 1-2 для білкових послідовностей та 2-4 для нуклеотидних) за вирахуванням штрафу за зроблені вставки.
2. Методом UPGMA (пізніше NJ) розраховується напрямне дерево, яким потім розраховуються ваги послідовностей, причому найближчі послідовності отримують менші ваги.
3. Відповідно до напрямного дерева вибираються найближчі послідовності і виконується їх вирівнювання методом динамічного програмування з використанням матриці замін і штрафів за відкриття/розширення вставок, з отриманим вирівнюванням зіставляються все нові послідовності.

Ітеративне вирівнювання. MUSCLE

Три стадії:

• швидке «чорнове» множинне вирівнювання (попарні глобальні вирівнювання; оцінка подібності як частка позицій, що збігаються; побудова напрямного дерева методом UPGMA або NJ; прогресивне вирівнювання)
• покращене множинне вирівнювання (оцінка подібності як частка збігаються позицій у поточному множинному вирівнюванні; побудова напрямного дерева через побудову матриці відстаней по Кімурі та її кластеризацію; порівняння поточного дерева з побудованим раніше; перерахунок вирівнювання для вузлів, що відрізняються);
• уточнення вирівнювання (видалення довільного вузла для розбиття дерева на два; побудова профілів для кожного піддерева та їх вирівнювання; розрахунок суми парних оцінок в множинному вирівнюванні, що виходить; перебір всіх вузлів від листя до кореня і вибір вирівнювання з максимальною сумою)