Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Ця стаття потребує упорядкування для відповідності стандартам якості Вікіпедії Будь ласка допоможіть поліпшити цю статтю

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

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

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

image
Перші 90 позицій множинного білкового вирівнювання на прикладі рибосомального білка P0 (L10E) з різних організмів, яке отримано за допомогою програми ClustalX.

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

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

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

Динамічне програмування та обчислювальна складність

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

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

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

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

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

Прогресивне вирівнювання не гарантує отримання оптимального глобального вирівнювання. Проблема полягає в тому, що помилки, отримані на будь-якій стадії зростаючого множинного вирівнювання, доходять до кінцевого вирівнювання. Крім того, вирівнювання може бути особливо поганим у випадку сильно віддалених одна від одної послідовностей. Більшість сучасних прогресивних методів мають змінену функцію обчислення ваги з вторинною ваговою функцією, яка присвоює коефіцієнти для окремих елементів набору даних у вигляді нелінійної моди заснованої на філогенетичній відстані від найближчих сусідів. Методи прогресивного вирівнювання досить ефективні, щоб застосовувати їх для великого числа (100—1000) послідовностей. Найпопулярніший метод прогресивного вирівнювання належить до сімейства Clustal, зокрема, варіант ClustalW, доступ до якого можна отримати через такі портали як 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 будує бібліотеку парних вирівнювань, яку потім використовує для побудови множинного вирівнювання.

Ітеративні методи

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

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

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

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

Консенсусні методи

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

Приховані марковські моделі

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

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

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

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

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

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

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

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

Методи, засновані на філогенетичному аналізі

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

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

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

Пошук мотивів

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

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

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

Примітки

  1. Огурцов, А. Н. (2013). (PDF) (російська) . Харків: НТУ "ХПИ". с. 196—211. ISBN . Архів оригіналу (PDF) за 5 лютого 2021. Процитовано 1 лютого 2021. {{}}: Перевірте значення |isbn=: довжина ()
  2. 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.
  3. 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.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. Mount D. M. Bioinformatics: Sequence and Genome Analysis 2nd ed. (англ.) // Cold Spring Harbor. — 2004.
  9. Higgins 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.
  10. Thompson 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.
  11. Кисляк С. В., Настенко Є. А (2018). (PDF) (українська) . Київ: КПІ ім. Ігоря Сікорського. с. 95. Архів оригіналу (PDF) за 7 лютого 2021. Процитовано 1 лютого 2021.
  12. . Архів оригіналу за 15 січня 2021.
  13. . Архів оригіналу за 31 грудня 2020.
  14. 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.
  15. . Архів оригіналу за 5 лютого 2021.
  16. 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.
  17. 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.
  18. . Архів оригіналу за 25 серпня 2010.
  19. . Архів оригіналу за 28 лютого 2021.
  20. 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.
  21. . Архів оригіналу за 27 квітня 2021.
  22. . Архів оригіналу за 13 січня 2021.
  23. Collingridge 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.
  24. Grasso C., Lee C. Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems. (англ.) // Bioinformatics. — 2004. — Vol. 20, no. 10. — P. 1546—1556. — doi:10.1093/bioinformatics/bth126. — PMID 14962922.
  25. . Архів оригіналу за 6 січня 2021.
  26. Hughey R, Krogh A. SAM: Sequence alignment and modeling software system. Technical Report UCSC-CRL-96-22, University of California, Santa Cruz, CA, September 1996.
  27. . Архів оригіналу за 16 січня 2021.
  28. Durbin R, Eddy S, Krogh A, Mitchison G. Biological sequence analysis: probabilistic models of proteins and nucleic acids. — Cambridge University Press, 1998. — ISBN 0-521-63041-4.
  29. Battey J. N., Kopp J., Bordoli L., Read R. J., Clarke N. D., Schwede T. Automated server predictions in CASP7. (англ.) // Proteins. — 2007. — Vol. 69 Suppl 8. — P. 68—82. — doi:10.1002/prot.21761. — PMID 17894354.
  30. Löytynoja A., Goldman N. An algorithm for progressive multiple alignment of sequences with insertions. (англ.) // Proceedings of the National Academy of Sciences of the United States of America. — 2005. — Vol. 102, no. 30. — P. 10557—10562. — doi:10.1073/pnas.0409137102. — PMID 16000407.
  31. . Архів оригіналу за 22 січня 2021.
  32. Löytynoja A., Goldman N. Phylogeny-aware gap placement prevents errors in sequence alignment and evolutionary analysis. (англ.) // Science (New York, N.Y.). — 2008. — Vol. 320, no. 5883. — P. 1632—1635. — doi:10.1126/science.1158395. — PMID 18566285.
  33. Lupyan D., Leo-Macias A., Ortiz A. R. A new progressive-iterative algorithm for multiple structure alignment. (англ.) // Bioinformatics. — 2005. — Vol. 21, no. 15. — P. 3255—3263. — doi:10.1093/bioinformatics/bti527. — PMID 15941743.
  34. Szalkowski A. M. Fast and robust multiple sequence alignment with phylogeny-aware gap placement. (англ.) // BMC bioinformatics. — 2012. — Vol. 13. — P. 129. — doi:10.1186/1471-2105-13-129. — PMID 22694311.
  35. Henikoff S., Henikoff J. G. Automated assembly of protein blocks for database searching. (англ.) // Nucleic acids research. — 1991. — Vol. 19, no. 23. — P. 6565—6572. — PMID 1754394.
  36. . Архів оригіналу за 28 січня 2021.
  37. Bailey T. L., Gribskov M. Combining evidence using p-values: application to sequence homology searches. (англ.) // Bioinformatics. — 1998. — Vol. 14, no. 1. — P. 48—54. — PMID 9520501.
  38. . Архів оригіналу за 25 червня 2019.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Cya stattya potrebuye uporyadkuvannya dlya vidpovidnosti standartam yakosti Vikipediyi Bud laska dopomozhit polipshiti cyu stattyu Mozhlivo storinka obgovorennya mistit zauvazhennya shodo potribnih zmin Mnozhinne virivnyuvannya poslidovnostej angl multiple sequence alignment MSA virivnyuvannya troh i bilshe biologichnih poslidovnostej zazvichaj bilkiv DNK abo RNK U bilshosti vipadkiv peredbachayetsya sho vhidnij nabir poslidovnostej maye evolyucijnij zv yazok Vikoristovuyuchi mnozhinne virivnyuvannya mozhna ociniti evolyucijne pohodzhennya poslidovnostej provivshi filogenetichnij analiz Pershi 90 pozicij mnozhinnogo bilkovogo virivnyuvannya na prikladi ribosomalnogo bilka P0 L10E z riznih organizmiv yake otrimano za dopomogoyu programi ClustalX Vizualizaciya virivnyuvannya ilyustruye mutacijni podiyi yak tochkovi mutaciyi zmina odniyeyi aminokisloti abo odnogo nukleotidu u viglyadi specialnih simvoliv v odnij kolonci virivnyuvannya a takozh gepi yih vstavki abo deleciyi zobrazhuyutsya znakom defisa Mnozhinne virivnyuvannya poslidovnostej chasto vikoristovuyetsya dlya ocinki konservativnosti domeniv bilkiv tretinnih i vtorinnih struktur i navit okremih aminokislotnih zalishkiv abo nukleotidiv Zvazhayuchi na bilshu obchislyuvalnu skladnist v porivnyanni z parnim virivnyuvannyam mnozhinne virivnyuvannya vimagaye bilsh skladni algoritmi Bagato program vikoristovuyut evristichni algoritmi oskilki poshuk globalnogo optimalnogo virivnyuvannya dlya bagatoh poslidovnostej mozhe zajmati trivalij chas Dinamichne programuvannya ta obchislyuvalna skladnistDlya bezposerednoyi pobudovi globalnogo optimalnogo virivnyuvannya vikoristovuyetsya dinamichne programuvannya Dlya bilkovih poslidovnostej isnuye dva nabori parametriv shtraf za gep i matricya zamin sho mistit v sobi jmovirnosti zistavlennya pari aminokislotnih zalishkiv yaki zasnovani na shozhosti yih himichnih vlastivostej i evolyucijnoyi jmovirnosti mutaciyi Dlya nukleotidnih poslidovnostej takozh vikoristovuyetsya shtraf za gep ale matricya zamin nabagato prostisha v nij vrahovuyutsya tilki zbigi nukleotidiv abo nespivpadinnya nukleotidiv mismatchi Dlya n okremih poslidovnostej nayivnij metod vimagaye pobudovi n mirnogo ekvivalenta matrici yaku vikoristovuyut dlya parnogo virivnyuvannya Z rostom n prostir poshuku zrostaye eksponencialno Takim chinom nayivnij algoritm maye obchislyuvalnu skladnist O Dovzhina poslidovnostejNposlidovnostej Poshuk globalnogo optimumu dlya n poslidovnostej vidnositsya do NP povnih zavdann U 1989 roci na osnovi algoritmu Karrilo Lipmana Altshul predstaviv praktichnij pidhid yakij vikoristovuvav parni virivnyuvannya dlya obmezhennya n mirnogo prostoru poshuku Pri takomu pidhodi dinamichne programuvannya vikonuyetsya na kozhnij pari poslidovnostej z vhidnogo naboru i provoditsya poshuk lishe dilyanki yaka roztashovana poblizu n mirnogo peretinu cih shlyahiv Programa optimizuye sumu vsih par simvoliv v kozhnij poziciyi virivnyuvanni Progresivne virivnyuvannyaProgresivne virivnyuvannya zastosovuye evristichnij algoritm rozroblenij Paulienoyu Hogeveg ta Benom Gesperom v 1984 roci Vsi metodi progresivnogo virivnyuvannya mayut dvi vazhlivi stadiyi pobudova binarnogo dereva dorogovkazivne derevo v yakomu listki ye poslidovnostyami i pobudova mnozhinnogo virivnyuvannya shlyahom dodavannya poslidovnostej do zrostayuchogo virivnyuvannya zgidno dorogovkazivnogo dereva Same dorogovkazivne derevo mozhe buti pobudovanim metodami klasterizaciyi takimi yak metod UPGMA i metod priyednannya susidiv Progresivne virivnyuvannya ne garantuye otrimannya optimalnogo globalnogo virivnyuvannya Problema polyagaye v tomu sho pomilki otrimani na bud yakij stadiyi zrostayuchogo mnozhinnogo virivnyuvannya dohodyat do kincevogo virivnyuvannya Krim togo virivnyuvannya mozhe buti osoblivo poganim u vipadku silno viddalenih odna vid odnoyi poslidovnostej Bilshist suchasnih progresivnih metodiv mayut zminenu funkciyu obchislennya vagi z vtorinnoyu vagovoyu funkciyeyu yaka prisvoyuye koeficiyenti dlya okremih elementiv naboru danih u viglyadi nelinijnoyi modi zasnovanoyi na filogenetichnij vidstani vid najblizhchih susidiv Metodi progresivnogo virivnyuvannya dosit efektivni shob zastosovuvati yih dlya velikogo chisla 100 1000 poslidovnostej Najpopulyarnishij metod progresivnogo virivnyuvannya nalezhit do simejstva Clustal zokrema variant ClustalW dostup do yakogo mozhna otrimati cherez taki portali yak GenomeNet EBI EMBNet ClustalW aktivno vikoristovuyetsya dlya pobudovi filogenetichnih derev nezvazhayuchi na poperedzhennya avtora sho neperevireni vruchnu virivnyuvannya ne povinni vikoristovuvatisya ni pri pobudovi derev ni v yakosti vhidnih danih dlya peredbachennya strukturi bilkiv Potochna versiya Clustal Clustal Omega yaka pracyuye na osnovi dorogovkazivnih derev i HMM profil profilnih metodiv dlya bilkovih virivnyuvan Shema metodu progresivnogo mnozhinnogo virivnyuvannya realizovanogo v programi Clustal Omega 1 Na samomu pochatku programa buduye vsi parni virivnyuvannya analizovanih poslidovnostej 2 Vidpovidno do parnih virivnyuvan otrimuyut matricyu evolyucijnih distancij 3 Formuyetsya klasterna diagrama filogenetichnogo derevo sho pobudovana vidpovidno do matrici evolyucijnih distancij 4 Vidpovidno do filogenetichnogo dereva programa buduye mnozhinne virivnyuvannya z vikoristannyam algoritmu globalnogo virivnyuvannya metodom dinamichnogo programuvannya Pislya provedennya parnogo globalnogo virivnyuvannya kozhnoyi poslidovnosti zi vsima na nastupnomu etapi rozrahovuyetsya distanciya mizh virivnyanimi poslidovnostyami Najprostishij sposib viznachennya genetichnoyi vidstani bazuyetsya na pidrahunku pozicij v virivnyuvanni de sposterigayutsya zamini Ultrametrichne filogenetichne derevo dozvolyaye zrobiti visnovki pro evolyucijne pohodzhennya danoyi grupi poslidovnostej ta vidibrati pari dlya yakih bude provedeno tak zvane dovirivnyuvannya Isnuyut rizni instrumenti dlya pobudovi progresivnogo virivnyuvannya poslidovnostej DNK Odin z nih MAFFT angl Multiple Alignment using Fast Fourier Transform Inshij poshirenij metod progresivnogo virivnyuvannya T Coffee povilnishij nizh Clustal i jogo pohidni ale najchastishe daye tochnishi virivnyuvannya dlya viddaleno pov yazanih poslidovnostej T Coffee buduye biblioteku parnih virivnyuvan yaku potim vikoristovuye dlya pobudovi mnozhinnogo virivnyuvannya Iterativni metodiNabir metodiv dlya pobudovi mnozhinnih virivnyuvan v yakih vidbuvayetsya znizhennya pomilok otrimanih progresivnimi metodami klasifikuyut yak iterativni Voni pracyuyut analogichno progresivnim metodam ale pri comu neodnorazovo perebudovuyut vihidni virivnyuvannya pri dodavanni novih poslidovnostej Progresivni metodi silno zalezhat vid yakosti pochatkovih virivnyuvan oskilki voni v nezminnomu viglyadi a otzhe i z pomilkami potraplyat v kincevij rezultat Inshimi slovami yaksho poslidovnist vzhe potrapila v virivnyuvannya yiyi podalshe stanovishe ne zminitsya Take nablizhennya pokrashuye efektivnist ale negativno poznachayetsya na tochnosti rezultatu Na vidminu vid progresivnih metodiv iterativni metodi mozhut povertatisya do spershu porahovanim parnim virivnyuvannya i pidvirivnyuvannyam sho mistyat pidmnozhini poslidovnostej iz zapitu i takim chinom optimizuvati zagalnu cilovu funkciyu i pidvishuvati yakist Isnuye velika kilkist riznomanitnih iterativnih metodiv Napriklad PRRN PRRP vikoristovuye algoritm shodzhennya do vershini dlya optimizaciyi vagi mnozhinnogo virivnyuvannya i iterativno koriguye vagi virivnyuvannya i dilyanki z velikoyu kilkistyu gepiv PRRP pracyuye efektivnishe koli pokrashuye virivnyuvannya poperedno pobudovane shvidkim metodom She odna iterativna programa DIALIGN vikoristovuye originalnij pidhid vona provodit lokalni virivnyuvannya pidsegmentiv abo motiviv poslidovnostej bez vvedennya shtrafu za gep Virivnyuvannya okremih motiviv realizuyetsya v matrichnomu viglyadi podibnomu do diagramoyu z tochkami dot plot v parnomu virivnyuvanni V programi CHAOS DIALIGN vikoristovuyetsya alternativnij metod yakij vikoristovuye shvidki lokalni virivnyuvannya v yakosti tochok priv yazki dlya bilsh povilnoyi proceduri pobudovi globalnogo virivnyuvannya Tretij populyarnij iteracijnij metod nazivayetsya MUSCLE Vin daye krashij rezultat nizh progresivni metodi oskilki vikoristovuye bilsh tochni vidstani dlya ocinki zv yazku dvoh poslidovnostej Cej metod realizuye onovlennya vidstanej mizh iteraciyami hocha v pervisnomu viglyadi MUSCLE mistiv tilki 2 3 iteraciyi Konsensusni metodiKonsensusni metodi namagayutsya vibrati optimalne mnozhinne virivnyuvannya z riznih mnozhinnih virivnyuvan odnogo i togo zh naboru vhidnih danih Isnuyut dva najbilsh poshirenih konsensusnih metodiv M COFFEE ta MergeAlign M COFFEE vikoristovuye mnozhinni virivnyuvannya sho generuyutsya 7 riznimi metodami dlya otrimannya konsensusnih virivnyuvan MergeAlign zdatnij generuvati konsensusni virivnyuvannya z bud yakogo chisla vhidnih virivnyuvan otrimanih z riznih modelej evolyuciyi poslidovnosti i metodiv pobudovi Opciya za zamovchuvannyam dlya MergeAlign vivedennya konsensusnogo virivnyuvannya vikoristovuyuchi virivnyuvannya otrimani z 91 riznih modelej evolyuciyi bilkovoyi poslidovnosti Prihovani markovski modeliDiv takozh Prihovana markovska model U bioinformatici metod prihovanih markovskih modelej Hidden Markov model HMM sluzhit dlya opisu tonkih vidminnostej sho isnuyut mizh simejstvami gomologichnih poslidovnostej Metod HMM efektivnij i pri prognozi shlyahiv zgortannya bilkiv Cej metod povnistyu bazuyetsya na analizi poslidovnostej tobto ne vikoristovuye strukturnu informaciyu Programi zasnovani na HMM predstavlyayut mnozhinne virivnyuvannya u viglyadi spryamovanogo aciklichnogo grafa vidomogo yak graf chastkovogo poryadku yakij skladayetsya z serij vuzliv yaki ye mozhlivimi stanami v kolonkah virivnyuvannya V takomu razi absolyutno konservativna kolonka tobto poslidovnosti yaki pri mnozhinnomu virivnyuvanni mayut v danij poziciyi pevnij simvol koduyetsya yak odin vuzol z bezlichchyu vihidnih z yednan z simvolami mozhlivimi v nastupnij poziciyi virivnyuvannya U terminah standartnoyi prihovanoyi markovskoyi modeli taki okremi kolonki virivnyuvannya ye stanami sposterigayutsya a prihovani stani yavlyayut soboyu peredbachuvanu predkovu poslidovnist vid yakoyi poslidovnosti vhidnogo naboru mogli evolyucinuvati Programi v yakih realizovanij metod NMM dlya analizu biologichnih poslidovnostej mozhut robiti nastupne 1 Navchannya Provoditsya virivnyuvannya vhidnogo naboru ne virivnyanih gomologichnih poslidovnostej i viznachennya NMM yaka opisuye zadanij nabir poslidovnostej dlya cogo provoditsya pidbir jmovirnostej perehodiv ta viboru zalishkiv 2 Poshuk dalekih gomologiv Mayuchi NMM i doslidzhuvanu poslidovnist mozhna rozrahuvati jmovirnist togo sho NMM mogla b zgeneruvati cyu poslidovnist Yaksho NMM rozroblena dlya vidomogo simejstva poslidovnostej mozhe ce zrobiti z dosit velikoyu jmovirnistyu to ce svidchit na korist togo sho doslidzhuvana poslidovnist takozh nalezhit do cogo simejstva 3 Virivnyuvannya dodatkovih poslidovnostej Imovirnist prohodzhennya bud yakogo marshrutu v danij NMM tobto jmovirnist otrimannya same danogo naboru staniv mozhe buti rozrahovana z individualnih jmovirnostej perehodiv stan za stanom state by state Nezvazhayuchi na te sho HMM metodi bilsh skladni nizh populyarni progresivni metodi isnuye kilka program dlya otrimannya virivnyuvan napriklad POA a takozh shozhij ale bilsh uzagalnenij metod v paketah SAM i HMMER HHsearch zasnovanij na parnomu porivnyanni HMMs vikoristovuyetsya dlya poshuku viddaleno pov yazanih poslidovnostej Server HHsearch HHpred buv najshvidshim z 10 krashih avtomatichnih serveriv vvikoristanih dlya peredbachennya struktur bilkiv CASP7 i CASP8 Metodi zasnovani na filogenetichnomu analiziBilshist metodiv mnozhinnogo virivnyuvannya namagayetsya minimizuvati kilkist gepiv vstavok chi delecij zavdyaki chomu generuyutsya kompaktni virivnyuvannya Takij pidhid mozhe prizvesti do pomilok u virivnyuvanni yaksho virivnyani poslidovnosti mistili negomologichnih regioni i yaksho gepi informativni pri filogenetichnomu analizi Ci problemi tipovi dlya novih poslidovnostej yaki pogano anotovani i mozhut mistiti zsuv ramki zchituvannya nepravilni domeni abo negomologichni splajsovani ekzoni Pershij metod zasnovanij na analizi filogeniyi buv rozroblenij Lojtinodzhom i Goldmanom v 2005 roci U 2008 roci ti zh avtori vipustili vidpovidne programne zabezpechennya PRANK PRANK udoskonalyuye virivnyuvannya koli ye vstavki Tim ne mensh vin pracyuye povilnishe nizh progresivni i abo iterativni metodi yaki buli rozrobleni za kilka rokiv do togo U 2012 roci z yavilisya dva novih metodi zasnovanih na filogenetichnomu analizi Pershij pid nazvoyu PAGAN buv rozroblenij komandoyu PRANK a drugij nazvanij ProGraphMSA buv rozroblenij Zhalkovskim Yih programne zabezpechennya bulo rozrobleno nezalezhno ale voni mayut zagalni risi obidva vikoristovuyut algoritmi na grafah dlya polipshennya rozpiznavannya negomologichnih regioniv pri comu voni shvidshi za metod PRANK Poshuk motivivPoshuk motiviv abo inakshe analiz profiliv ce metod poshuku lokalizaciyi motivu v globalnomu mnozhinnomu virivnyuvanni yak zasib otrimannya krashogo MSA i serednovagovoyi matrici z metoyu vikoristannya yiyi dlya poshuku inshih poslidovnostej z podibnimi motivami Bulo rozrobleno veliku kilkist metodiv dlya viznachennya motiviv ale vsi voni gruntuyutsya na viyavlenni korotkih visokokonservativnih paterniv v bilshomu po dovzhini virivnyuvannya paterni i konstruyuvanni matrici podibnoyi do matrici zamin Cya matricya vidobrazhaye nukleotidnij abo aminokislotnij sklad dlya kozhnoyi poziciyi v peredbachuvanomu motivi Potim virivnyuvannya mozhe buti utochneno za dopomogoyu cih matric U standartnomu analizi profiliv cya matricya vklyuchaye v sebe zapis yak dlya kozhnogo mozhlivogo simvolu tak i dlya gepa Na protivagu comu statistichnij algoritm poshuku paterniv spochatku shukaye motivi a potim vikoristovuye znajdeni motivi dlya pobudovi mnozhinnogo virivnyuvannya U bagatoh vipadkah koli vhidnij nabir poslidovnostej mistit neveliku kilkist poslidovnostej abo viklyuchno visoko sporidneni poslidovnosti dodayutsya en dlya normalizaciyi rozpodilu vidobrazhenogo u vagovij matrici Zokrema ce dopomagaye unikati nuliv v matrici jmovirnostej shob ne otrimati znachennya neskinchennosti v pozicijnij vagovij matrici Analiz blokiv ce metod poshuku motiviv v dilyankah virivnyuvannya bez gepiv Bloki mozhut buti zgenerovani z mnozhinnogo virivnyuvannya abo otrimani z nevirivnyanih poslidovnostej shlyahom poperednogo rozrahunku mnozhini zagalnih motiviv vidomih simejstv geniv Ocinka blokiv zazvichaj gruntuyetsya na prostori simvoliv z visokoyu chastotoyu nayavnosti v blokah a ne na obchislenni v yavnomu viglyadi matric zamin Server BLOCKS nadaye alternativnij metod dlya lokalizaciyi takih motiviv v nevirivnyani poslidovnosti Statistichne zistavlennya paterniv zdijsnyuyetsya za dopomogoyu algoritmu maksimizaciyi ochikuvannya i semplyuvannya za Gibbsom Dlya poshuku motiviv najbilsh chasto vikoristovuyetsya server MEME sho vikoristovuye algoritm maksimizaciyi ochikuvannya i metod prihovanih markovskih modelej a takozh MEME MAST yakij dodatkovo vikoristovuye algoritm MAST PrimitkiOgurcov A N 2013 PDF rosijska Harkiv NTU HPI s 196 211 ISBN 978 617 05 069 4 Arhiv originalu PDF za 5 lyutogo 2021 Procitovano 1 lyutogo 2021 a href wiki D0 A8 D0 B0 D0 B1 D0 BB D0 BE D0 BD Cite book title Shablon Cite book cite book a Perevirte znachennya isbn dovzhina dovidka Wang L Jiang T On the complexity of multiple sequence alignment angl 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 angl 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 angl 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 Carrillo H Lipman D J The Multiple Sequence Alignment Problem in Biology angl SIAM Journal of Applied Mathematics 1988 Vol 48 no 5 P 1073 1082 doi 10 1137 0148063 Lipman D J Altschul S F Kececioglu J D A tool for multiple sequence alignment angl Proceedings of the National Academy of Sciences of the United States of America 1989 Vol 86 no 12 P 4412 4415 PMID 2734293 Hogeweg P Hesper B The alignment of sets of sequences and the construction of phyletic trees an integrated method angl Journal of molecular evolution 1984 Vol 20 no 2 P 175 186 PMID 6433036 Mount D M Bioinformatics Sequence and Genome Analysis 2nd ed angl Cold Spring Harbor 2004 Higgins D G Sharp P M CLUSTAL a package for performing multiple sequence alignment on a microcomputer angl Gene 1988 Vol 73 no 1 P 237 244 PMID 3243435 Thompson 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 angl Nucleic acids research 1994 Vol 22 no 22 P 4673 4680 PMID 7984417 Kislyak S V Nastenko Ye A 2018 PDF ukrayinska Kiyiv KPI im Igorya Sikorskogo s 95 Arhiv originalu PDF za 7 lyutogo 2021 Procitovano 1 lyutogo 2021 Arhiv originalu za 15 sichnya 2021 Arhiv originalu za 31 grudnya 2020 Notredame C Higgins D G Heringa J T Coffee A novel method for fast and accurate multiple sequence alignment angl Journal of molecular biology 2000 Vol 302 no 1 P 205 217 doi 10 1006 jmbi 2000 4042 PMID 10964570 Arhiv originalu za 5 lyutogo 2021 Gotoh O Significant improvement in accuracy of multiple protein sequence alignments by iterative refinement as assessed by reference to structural alignments angl Journal of molecular biology 1996 Vol 264 no 4 P 823 838 doi 10 1006 jmbi 1996 0679 PMID 8980688 Brudno M Chapman M Gottgens B Batzoglou S Morgenstern B Fast and sensitive multiple alignment of large genomic sequences angl BMC bioinformatics 2003 Vol 4 P 66 doi 10 1186 1471 2105 4 66 PMID 14693042 Arhiv originalu za 25 serpnya 2010 Arhiv originalu za 28 lyutogo 2021 Edgar R C MUSCLE multiple sequence alignment with high accuracy and high throughput angl Nucleic acids research 2004 Vol 32 no 5 P 1792 1797 doi 10 1093 nar gkh340 PMID 15034147 Arhiv originalu za 27 kvitnya 2021 Arhiv originalu za 13 sichnya 2021 Collingridge P W Kelly S MergeAlign improving multiple sequence alignment performance by dynamic reconstruction of consensus multiple sequence alignments angl BMC bioinformatics 2012 Vol 13 P 117 doi 10 1186 1471 2105 13 117 PMID 22646090 Grasso C Lee C Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems angl Bioinformatics 2004 Vol 20 no 10 P 1546 1556 doi 10 1093 bioinformatics bth126 PMID 14962922 Arhiv originalu za 6 sichnya 2021 Hughey R Krogh A SAM Sequence alignment and modeling software system Technical Report UCSC CRL 96 22 University of California Santa Cruz CA September 1996 Arhiv originalu za 16 sichnya 2021 Durbin R Eddy S Krogh A Mitchison G Biological sequence analysis probabilistic models of proteins and nucleic acids Cambridge University Press 1998 ISBN 0 521 63041 4 Battey J N Kopp J Bordoli L Read R J Clarke N D Schwede T Automated server predictions in CASP7 angl Proteins 2007 Vol 69 Suppl 8 P 68 82 doi 10 1002 prot 21761 PMID 17894354 Loytynoja A Goldman N An algorithm for progressive multiple alignment of sequences with insertions angl Proceedings of the National Academy of Sciences of the United States of America 2005 Vol 102 no 30 P 10557 10562 doi 10 1073 pnas 0409137102 PMID 16000407 Arhiv originalu za 22 sichnya 2021 Loytynoja A Goldman N Phylogeny aware gap placement prevents errors in sequence alignment and evolutionary analysis angl Science New York N Y 2008 Vol 320 no 5883 P 1632 1635 doi 10 1126 science 1158395 PMID 18566285 Lupyan D Leo Macias A Ortiz A R A new progressive iterative algorithm for multiple structure alignment angl Bioinformatics 2005 Vol 21 no 15 P 3255 3263 doi 10 1093 bioinformatics bti527 PMID 15941743 Szalkowski A M Fast and robust multiple sequence alignment with phylogeny aware gap placement angl BMC bioinformatics 2012 Vol 13 P 129 doi 10 1186 1471 2105 13 129 PMID 22694311 Henikoff S Henikoff J G Automated assembly of protein blocks for database searching angl Nucleic acids research 1991 Vol 19 no 23 P 6565 6572 PMID 1754394 Arhiv originalu za 28 sichnya 2021 Bailey T L Gribskov M Combining evidence using p values application to sequence homology searches angl Bioinformatics 1998 Vol 14 no 1 P 48 54 PMID 9520501 Arhiv originalu za 25 chervnya 2019

Дата публікації:
Топ