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

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

Алгоритми вирівнювання послідовностей також використовуються в NLP.


1. Графічне та текстове представлення

У більшості подань результату вирівнювання, послідовності розташовуються в рядках матриці таким чином, що співпадаючі елементи (нуклеотиди або амінокислоти) знаходяться один під іншим (в одній колонці). "Розриви" замінюються знаком "-" або осередок залишається порожньою.

Вирівнювання двох послідовностей амінокислот (" цинкових пальців "), згенероване програмою ClustalW. В лівій колонці знаходяться ідентифікатори цих послідовностей в базі GenBank.
Позначення: Букви - Амінокислоти. Знаки: "*" - однакові. "." - В одній колірній групі. ":" - Однакової форми.

2. Попарне вирівнювання

Попарне вирівнювання використовується для знаходження співпадаючих ділянок двох послідовностей. Розрізняють глобальне і локальне вирівнювання. Глобальне вирівнювання застосовується до "схожим" послідовностям приблизно однакової довжини і наочно показує різницю між цими послідовностями. Локальне вирівнювання застосовується для переважно відрізняються один від одного послідовностей, які ймовірно можуть містять однакові ділянки. Наступний приклад демонструє різницю між результатами глобального і локального вирівнювання для однакових вихідних даних

  • Глобальне

SQ1: FTFTALILLAVAV
SQ2: F - TAL-LLA-AV

  • Локальне

SQ1: FTFTALILL-AVAV
SQ2: - FTAL-LLAAV -


Глобальне вирівнювання базується на алгоритмі Нідлмана-Вунш, локальне - на алгоритмі Сміта-Ватермана.


2.1. Алгоритми пошуку

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

3. Множинне вирівнювання

По суті є попарним вирівнюємо всіх послідовностей в неком наборі і знаходження найбільш "оптимального" загального вирівнювання. Застосовується переважно для знаходження консервативних регіонів в наборі послідовностей. Також використовується в процесах встановлення еволюційних зв'язків шляхом побудови філогенетичних дерев. Так як множинне вирівнювання є NP-повною задачею [2] [3], різні її рішення базуються на евристики, генетичних та інших алгоритмах комбінаторної оптимізації. Найбільш відомі програми, що здійснюють множинне вирівнювання - Clustal ([2]), T-coffee, MUSCLE (http://www.drive5.com/muscle/) і MAFFT (http://mafft.cbrc.jp/alignment/software/).


4. Структурне вирівнювання

Застосовується до білків і RNA-послідовностям, для яких відома їх вторинна і / або третинна структура.

Примітки

  1. Mount DM. Bioinformatics: Sequence and Genome Analysis. - 2nd. - Cold Spring Harbor Laboratory Press: Cold Spring Harbor, NY., 2004. - ISBN 0-87969-608-7
  2. Wang L, Jiang T. (1994). "On the complexity of multiple sequence alignment". J Comput Biol 1 (4): 337-48. PMID 8790475.
  3. Just W. (2001). Computational complexity of multiple sequence alignment with SP-score. J Comput Biol 8 (6) :615-23.