Informație

Care este cea mai bună definiție de aliniere pentru problema MSA (Multiple Sequence Alignment)?


Pentru simplitate, să presupunem că penalizez nepotrivirile și decalajele cu -1 și adaug un scor +100 pentru fiecare meci. Realizează alinierea optimă a celor trei secvențe de ADN

AAATTT

AAAGGG

GGGAAC

egal cu:

AAATTT---

AAAGGG---

---GGGAAC

cu scorul total S = 294 + 294 - 6 = 586? În acest caz, însumez scorul de aliniere pentru fiecare dintre cele trei perechi.

Sau este egal cu:

---AAATT

---AAAGGG

GGGAAC---

cu scorul 200 - 7 = 193? În acest caz, recompensez doar potrivirile care au avut loc în toate cele trei secvențe în același timp.

Pentru care dintre cele două scoruri încearcă să optimizeze algoritmii comuni de aliniere a secvenței multiple? Sau dacă ambele sunt valide, atunci care aliniere optimă (adică în raport cu ce definiție) este preferată dacă au fost folosite valori realiste de recompensă/penalizare?


În cazul dumneavoastră, ambele răspunsuri sunt la fel de valide.

Matricea de punctaj, de exemplu DNAFULL (http://rosalind.info/glossary/dnafull/) conține de obicei diverse penalități pentru alinieri greșite.

De asemenea, scorul de introducere a decalajului nu ar trebui să fie NICIODATĂ setat la 0, deoarece va face ca secvențele aliniate să fie umplute cu goluri artificiale!

Singurul lucru pe care algoritmii încearcă să-l optimizeze este scorul, prin urmare aveți nevoie de valori sănătoase pentru calcularea scorului, iar cele pe care le propuneți nu au ca rezultat alinieri utile.


Etichete [alignment], [sequence-alignment], [read-alignment] și [msa]

Să decidem aici starea diferitelor etichete legate de aliniere.

Există două grupuri de întrebări.

Unul este legat de alinieri de secvențe perechi și multiple și algoritmi. Acest domeniu este cu siguranță vechi și a fost una dintre cheile de boltă în dezvoltarea bioinformaticii. Primiți întrebări precum instrumente de aliniere care acceptă codoni, editarea alinierii ARN sau alinierea completă a genomului.

Altul este legat de citiți alinierea/matarea. Primim în principal întrebări legate de software-ul de cartografiere, cum ar fi obținerea de citiri mapate unic, scorul BWA-MEM sau construirea indexului genomului.

Desigur, citirea alinierii este o serie de pași de aliniere a secvenței. În practică, totuși, majoritatea întrebărilor actuale [de aliniere] sunt specifice doar pentru citirea software-ului de cartografiere și nu au nimic de-a face cu metodele de aliniere a secvenței.

Cred că trebuie să ne gândim la etichete în mod pragmatic, este o modalitate prin care oamenii să o facă urmează ceea ce îi interesează, și în mod clar aceste două domenii sunt de interes pentru oameni diferiti. În această linie, este de remarcat faptul că meta-etichetele sunt considerate inutile și ar trebui evitate.

  • Dacă eticheta nu poate funcționa ca singura etichetă pentru o întrebare, este probabil o metaetichetă
  • Dacă eticheta înseamnă de obicei lucruri diferite pentru diferiți oameni, este probabil o metaetichetă

Acestea sunt rezultatele din laboratorul nostru destul de divers, unde unii oameni lucrează cu date ARN-seq. În mod clar, doar [alinierea] este ambiguă.

În forma actuală [alignment] este o meta-etichetă.

Metaetichetarea este descurajată în mod explicit.

Văd două moduri de a trata asta.


Alinierea globală eficientă și robustă a secvenței de aminoacizi cu distanță evolutivă incertă

Matthias C.M. Troffaes, în Procesarea modernă a informațiilor, 2006

2.1. Ce este alinierea secvenței?

O aliniere a secvenței constă în scrierea a două (sau mai multe) secvențe pe rânduri și scrierea caracterelor similare în aceeași coloană. Procedând astfel, i se permite să introducă așa-numitele goluri, notat printr-o liniuță „–” în oricare dintre secvențe. Presupunând că secvențele sunt derivate dintr-o secvență strămoșească comună, potrivirile corespund regiunilor conservate, nepotrivirile corespund mutațiilor și golurile corespund ștergerii sau inserțiilor, numite pe scurt indelii, în oricare dintre secvențe.

Figura 1 oferă un exemplu de aliniere a aminoacizilor.

Fig. 1. Un extract dintr-o posibilă aliniere a lanțurilor alfa și beta de hemoglobină [7].

Este convenabil să se reprezinte aliniamente într-o grilă, așa cum este prezentat în Figura 2. Toate căile de la colțul din stânga sus până la colțul din dreapta jos reprezintă aliniamente posibile. Calea desenată în Figura 2 corespunde aliniamentului dat în Figura 1 . O mișcare în diagonală nu introduce goluri, o mișcare în jos introduce un decalaj în

Fig. 2. Alinierea poate fi reprezentată convenabil într-o grilă.

secvența superioară, o mișcare spre dreapta introduce un gol în secvența inferioară.

Când încercăm să explicăm relațiile evolutive dintre secvențe, ar trebui să identificăm alinierea care are cele mai mari șanse de a fi rezultatul evoluției și, ca atare, să identificăm rezultatul evoluției dintr-un strămoș comun. Mai întâi arătăm cum dinamica evolutivă poate fi descrisă la nivel de secvențe genetice. Apoi arătăm cum se obține o matrice de scor din aceste dinamice și cum problema de optimizare rezultată identifică într-adevăr alinierea care are cele mai mari șanse de a fi rezultatul evoluției dintr-un strămoș comun.


Rezumat: Alinierea secvenței multiple (MSA) este un pas important în analizele de secvențe comparative. Paralelizarea este o tehnică cheie pentru reducerea timpului necesar analizelor de secvențe la scară largă. Cele trei etape de calcul, comparație all-to-all, aliniere progresivă și rafinare iterativă, ale programului MAFFT MSA au fost paralelizate folosind biblioteca POSIX Threads. Două strategii de paralelizare naturală (best-first și simplă alpinism) au fost implementate pentru etapa de rafinare iterativă. Pe baza comparațiilor dintre scorurile obiectivelor și scorurile de referință dintre cele două abordări, am selectat o abordare simplă de alpinism ca implicită.

Disponibilitate: Versiunea paralelizată a MAFFT este disponibilă la http://mafft.cbrc.jp/alignment/software/. Această versiune acceptă în prezent numai sistemul de operare Linux.

Informatie suplimentara: Date suplimentare sunt disponibile la Bioinformatica pe net.

Procesoarele cu mai multe nuclee devin din ce în ce mai obișnuite. Acest tip de CPU poate efectua diverse analize bioinformatice în paralel, inclusiv căutări în baze de date, în care sarcinile pot fi împărțite în mai multe părți (ex. Mathog, 2003). Paralelizarea unui calcul de aliniere a secvenței multiple (MSA) este o problemă complicată, deoarece sarcina nu poate fi împărțită în mod natural în părți independente. Astfel, au existat mai multe rapoarte privind paralelizarea calculelor de aliniere multiple cu diverși algoritmi pe diferite tipuri de sisteme computerizate paralele (Chaichoompu et al., 2006 Data et al., 1993 Ishikawa et al., 1993 Kleinjung et al., 2002 Li, 2003). Prezentul studiu vizează un tip de PC popular în prezent, care are 1–2 procesoare(i), fiecare cu 1–4 nuclee(i) și spațiu de memorie partajat.

MAFFT (Katoh et al., 2002 Katoh și Toh, 2008) este un program popular MSA. Pentru a-și îmbunătăți utilitatea pe computerele multi-core, am implementat o versiune paralelizată, folosind biblioteca POSIX Threads (pthreads). Scopul este de a paraleliza eficient MAFFT, păstrând în același timp calitatea rezultatelor. Procedura de calcul a opțiunilor majore ale MAFFT constă din trei etape: (i) comparație totală, (ii) aliniere progresivă și (iii) rafinare iterativă.

Nu există nicio problemă în paralelizarea primei etape, comparația all-to-all. Firele multiple pot procesa diferite alinieri pe perechi simultan și independent, cu o mică pierdere de timp CPU.

În stadiul de aliniere progresivă (Feng și Doolittle, 1987 Thompson et al., 1994), calculele de aliniere de la grup la grup sunt efectuate împreună cu un arbore de ghidare. Acest proces nu este foarte potrivit pentru paralelizare, deoarece ordinea calculelor de aliniere este restricționată de arborele de ghidare. Adică, o aliniere la un nod nu poate fi efectuată până când toate aliniamentele din nodurile sale secundare nu au fost finalizate. Atâta timp cât această restricție este menținută, aliniamentele pot fi efectuate la nodurile copil care sunt independente unul de celălalt. Astfel, în implementarea noastră, eficiența paralelizării este inevitabil scăzută în această etapă. Deși este posibil să se proiecteze un arbore ghid care să fie potrivit pentru paralelizare (Li, 2003), nu am adoptat această abordare, deoarece în MAFFT această etapă consumă mai puțin timp CPU decât celelalte două (pentru detalii vezi Tabelul suplimentar, în care procentul de timp de execuție al acestei etape este sub 2%).

În fiecare pas al procesului de rafinare iterativă (Barton și Sternberg, 1987 Berger și Munson, 1991 Gotoh, 1993), un aliniament este împărțit în două sub-alinieri și apoi cele două sub-aliniamente sunt realiniate, conform strategiei iterative dependente de arbore ( Gotoh, 1996 Hirosawa et al., 1995), pentru a obține o aliniere cu un scor obiectiv mai mare. Am implementat cea mai bună abordare-prima și o abordare simplă de alpinism pentru această etapă.

În cea mai bună abordare, realinările sunt efectuate pentru toate cele 2 posibileN − 3 diviziuni pe arbore, iar apoi este selectată alinierea cu cel mai mare punctaj obiectiv, unde N este numărul de secvențe. Acest proces se repetă până când nu se găsește nicio aliniere cu un scor mai mare. Deoarece doar alinierea cu cel mai mare scor contribuie la pasul următor, iar celelalte aliniamente sunt eliminate, această abordare este evident ineficientă.

Ca o alternativă, în care sunt aruncate mai puține aliniamente, am implementat o abordare simplă de alpinism. Procesele de realiniere sunt atribuite aleatoriu mai multor fire și efectuate în paralel. Dacă scorul unei noi alinieri de către un fir este mai bun decât alinierea inițială, atunci acesta înlocuiește instantaneu alinierea inițială. În consecință, poate exista un caz în care două sau mai multe fire diferite în paralel produc aliniamente diferite și mai bune. Într-un astfel de caz, prima aliniere (în termeni de timp) este selectată, în timp ce celelalte aliniamente sunt eliminate. Abordarea simplă de alpinism este de așteptat să fie eficientă atunci când numărul de fire este mic. Odată cu creșterea numărului de fire, numărul de aliniamente aruncate crește și astfel eficiența va scădea. Alinierea rezultată depinde de numere aleatorii.

Cea mai bună abordare primul oferă un rezultat stabil independent de numere aleatorii, în timp ce abordarea simplă de alpinism are în general un avantaj, în ceea ce privește viteza. Prin urmare, am examinat care este mai potrivit pentru problema de aliniere multiplă. Pentru a compara eficiența acestora, cea mai simplă opțiune de rafinare iterativă fără ponderare a secvenței a fost aplicată tuturor celor 218 aliniamente din BAliBASE versiunea 3 (Thompson et al., 2005). Abordarea simplă de alpinism a fost efectuată de 10 ori cu numere aleatorii diferite. Pentru fiecare dintre cursele de 218 × 10 cu abordarea simplă de alpinism, scorul obiectivului final a fost comparat cu scorul obiectivului final obținut din abordarea cea mai bună-prima. Prima a fost mai mare decât cea din urmă în 972 de cazuri, în timp ce prima a fost mai mică decât cea din urmă în 917 cazuri. În restul de 291 de cazuri, cele două aliniamente au fost identice una cu cealaltă. Acest rezultat raționalizează utilizarea abordării simple de alpinism.

Pentru a confirma că acuratețea aliniamentelor prin cele două abordări nu se disting una de cealaltă și de cea generată de versiunea în serie, au fost calculate și scorurile de referință BAliBASE, unde diferențele față de aliniamentele de referință (presupuse a fi corecte) au fost evaluate ca scorurile SP și TC (Thompson et al., 1999). Scorurile medii generale SP ale uneia dintre cele mai precise opțiuni MAFFT, L-INS-i, au fost 0,8728 ± 0,0003649 (media simplă de alpinism ± SD), 0,8720 (cel mai bun primul) și 0,8722 (versiunea de serie). Scorurile medii generale ale TC au fost 0,5926 ± 0,001162 (alpinism simplu), 0,5927 (cel mai bun primul) și 0,5928 (versiunea în serie). Media și SD-ul scorurilor abordării simple de alpinism au fost calculate din 10 alergări cu numere aleatorii diferite.

Figura 1 arată timpul real necesar pentru a calcula cea mai mare aliniere (BB30003 142 secvențe × 451 locuri, inclusiv goluri) în BAliBASE, folosind numere diferite (1–16) de fire de execuție pe un PC cu 16 nuclee (4 × Procesor AMD Opteron 8378 Quad-Core ). Când numărul de fire este opt, eficiența paralelizării este de 0,89 și 0,55 pentru abordarea cea mai bună-prima și, respectiv, abordarea simplă de alpinism. După cum era de așteptat, pierderea vitezei în abordarea simplă de alpinism crește odată cu creșterea numărului de fire. Acest lucru se datorează faptului că numărul de aliniamente aruncate crește, așa cum sa menționat mai sus. Pierderea de viteză pentru abordarea cea mai bună, prima este relativ mică. Cu toate acestea, în intervalul sistemelor țintă din prezentul studiu (PC-uri multi-core obișnuite), abordarea simplă de alpinism este mai rapidă și, prin urmare, a fost adoptată ca implicită.

Eficiența paralelizării pentru o opțiune de rafinare iterativă (L-INS-i) cu două strategii de paralelizare (cel mai bun primul și simplu alpinism) și o opțiune progresivă (L-INS-1). Liniile corespund situației ideale în care (Timp scurs cu n fire) = (Timp scurs cu un singur fir) / n. Argumentele liniei de comandă sunt: ​​Best-first, mafft-linsi --bestfirst --thread n intrare Simple hill-climbing, mafft-linsi --thread n intrare Progresiv, mafft-linsi --maxiterate 0 --thread n intrare

Eficiența paralelizării pentru o opțiune de rafinare iterativă (L-INS-i) cu două strategii de paralelizare (cel mai bun primul și simplu alpinism) și o opțiune progresivă (L-INS-1). Liniile corespund situației ideale în care (Timp scurs cu n fire) = (Timp scurs cu un singur fir) / n. Argumentele liniei de comandă sunt: ​​Best-first, mafft-linsi --bestfirst --thread n intrare Simple hill-climbing, mafft-linsi --thread n intrare Progresiv, mafft-linsi --maxiterate 0 --thread n intrare

Am examinat, de asemenea, aplicabilitatea abordării simple de alpinism la date mai mari. După cum se arată în tabelul suplimentar, eficiența cu opt fire este de 0,55–0,74 pentru cinci seturi de date, fiecare cu aproximativ 1000 de secvențe.

Versiunile MAFFT ≥6.8 trec la versiunea pthread prin simpla adăugare a --thread n argument, unde n este numărul de fire de folosit. Nu este necesară nicio configurație specială pentru procesarea paralelă pe un PC multi-core cu sistemul de operare Linux.


Instrumente de bioinformatică: alinierea secvenței

După cum indică numele lor, instrumentele de aliniere a secvenței locale în perechi sunt folosit pentru a găsi regiuni de secvență similară sau identică între o pereche de secvențe de ADN, ARN sau proteine.

Utilizările obișnuite ar fi alinierea perechilor de mutanți ai secvenței de proteine ​​sau ADN. Aceste programe sunt, de asemenea, foarte utile pentru alinierea și compararea datelor de secvențiere ADN cu secvența unei gene cunoscute sau a unui șablon ADN parental.

Apă emboss

Alinierea secvenței în perechi folosind un algoritm Smith-Waterman modificat. Perechile de secvențe trebuie furnizate fie în format GCG, FASTA, EMBL, GenBank, PIR, NBRF, Phylip sau UniProtKB/Swiss-Prot.

emboss matchcher

Alinierea secvenței în perechi bazată pe aplicația LALIGN. Perechile de secvențe trebuie furnizate fie în format GCG, FASTA, EMBL, GenBank, PIR, NBRF, Phylip sau UniProtKB/Swiss-Prot.

Despre Clustal Omega:

Clustal Omega este un instrument de aliniere a secvențelor multiple cel mai bine utilizat pentru alinierea regiunilor de secvență similare între trei sau mai multe secvențe de ARN, ADN sau proteine. Timp de mulți ani, versiunea anterioară a instrumentului, Clustal W, a fost utilizată pe scară largă pentru acest tip de aliniere a secvenței multiple. Clustal Omega este o versiune îmbunătățită a acestui instrument.

Formatele de secvență acceptate sunt GCG, FASTA, EMBL, GenBank, PIR, NBRF, PHYLIP sau UniProtKB/Swiss-Prot. Versiunea actuală a software-ului acceptă maximum 2000 de secvențe. Fișierele de secvență încărcate sunt limitate la maximum 2 MB.

Servere web găzduite:

Aplicația poate fi utilizată online prin servere web găzduite în următoarele locații:

Descărcarea aplicației pe computerul personal:

Programul Clustal Omega poate fi descărcat și pentru utilizare independentă pe computerele personale care rulează sisteme de operare Mac, Windows sau Linux din următoarea locație:

Descărcarea JalView Sequence Alignment Results Viewer:

Deși Clustal Omega oferă o afișare utilă bazată pe text a rezultatelor alinierii, vizualizatorul JalView de rezultate de aliniere oferă o modalitate mult mai plăcută de a face acest lucru. Puteți descărca programul de instalare corespunzător al aplicației de aici:

Sievers F, Söding J, Thompson JD, Higgins DG, Wilm A, Dineen D, Gibson TJ, Karplus K, Li W, Lopez R și colab. . 2011. Generare rapidă, scalabilă de alinieri de secvențe multiple de proteine ​​de înaltă calitate folosind Clustal Omega. Biologia sistemelor moleculare 7(1):1-6.

Despre Instrumentul de căutare de bază pentru alinierea locală (BLAST):

Instrumentul de căutare de bază pentru alinierea locală (BLAST) vă permite să efectuați aliniamente locale între o secvență de ADN, ARN sau proteină furnizată de utilizator și secvențele conținute într-un număr mare de baze de date de secvențe organizate (de exemplu, secvențe de genom asamblate, etichete de secvență exprimată (EST), genomi NCBI, secvențe de proteine ​​brevetate, proteine ​​din baza de date de proteine ​​(pdb) etc.).

Suita BLAST oferă interfețe separate pentru multe comparații diferite de secvențe de interogări/baze de date. Cele mai frecvent utilizate instrumente de aliniere sunt furnizate cu descrieri și link-uri mai jos:

O secvență de nucleotide furnizată de utilizator este comparată cu o bază de date selectată de secvențe de nucleotide.

O secvență de proteine ​​furnizată de utilizator este comparată cu o bază de date de secvențe de proteine ​​selectate.

O secvență de nucleotide furnizată de utilizator este utilizată pentru a genera secvențe de proteine ​​dintr-un in Silicon Translație cu 6 cadre. Fiecare dintre cele șase secvențe de proteine ​​rezultate este comparată cu o bază de date de secvențe de proteine ​​selectate.

O secvență de proteine ​​furnizată de utilizator este comparată cu secvențele de proteine ​​rezultate din in Silicon 6 translație de cadre a unei baze de date de secvențe de nucleotide selectate.

O secvență de nucleotide furnizată de utilizator este utilizată pentru a genera secvențe de proteine ​​dintr-un in Silicon Translație cu 6 cadre. Fiecare dintre cele șase secvențe de proteine ​​rezultate este comparată cu secvențele de proteine ​​rezultate din in Silicon 6 translație de cadre a unei baze de date de secvențe de nucleotide selectate. Deci, deși atât interogarea inițială, cât și baza de date de comparație sunt secvențe de nucleotide, rezultatele TBLAST-X sunt furnizate ca alinieri de secvență de proteine.


Paralelizarea programului de aliniere a secvenței multiple MAFFT

Rezumat: Alinierea secvenței multiple (MSA) este un pas important în analizele comparative de secvențe. Paralelizarea este o tehnică cheie pentru reducerea timpului necesar analizelor de secvențe la scară largă. Cele trei etape de calcul, comparație all-to-all, aliniere progresivă și rafinare iterativă, ale programului MAFFT MSA au fost paralelizate folosind biblioteca POSIX Threads. Două strategii de paralelizare naturală (best-first și simplă alpinism) au fost implementate pentru etapa de rafinare iterativă. Pe baza comparațiilor dintre scorurile obiectivelor și scorurile de referință dintre cele două abordări, am selectat o abordare simplă de alpinism ca implicită.

Disponibilitate: Versiunea paralelizată a MAFFT este disponibilă la http://mafft.cbrc.jp/alignment/software/. Această versiune acceptă în prezent numai sistemul de operare Linux.

Informatie suplimentara: Date suplimentare sunt disponibile la Bioinformatica pe net.

Procesoarele cu mai multe nuclee devin din ce în ce mai obișnuite. Acest tip de CPU poate efectua diverse analize bioinformatice în paralel, inclusiv căutări în baze de date, în care sarcinile pot fi împărțite în mai multe părți (ex. Mathog, 2003). Paralelizarea unui calcul de aliniere a secvenței multiple (MSA) este o problemă complicată, deoarece sarcina nu poate fi împărțită în mod natural în părți independente. Astfel, au existat mai multe rapoarte privind paralelizarea calculelor de aliniere multiple cu diverși algoritmi pe diferite tipuri de sisteme computerizate paralele (Chaichoompu et al., 2006 Data et al., 1993 Ishikawa et al., 1993 Kleinjung et al., 2002 Li, 2003). Prezentul studiu vizează un tip de PC popular în prezent, care are 1𠄲 procesor(e), fiecare cu 1𠄴 nuclee(i) și spațiu de memorie partajat.

MAFFT (Katoh et al., 2002 Katoh și Toh, 2008) este un program popular MSA. Pentru a-și îmbunătăți utilitatea pe computerele multi-core, am implementat o versiune paralelizată, folosind biblioteca POSIX Threads (pthreads). Scopul este de a paraleliza eficient MAFFT, păstrând în același timp calitatea rezultatelor. Procedura de calcul a opțiunilor majore ale MAFFT constă din trei etape: (i) comparație totală, (ii) aliniere progresivă și (iii) rafinare iterativă.

Nu există nicio problemă în paralelizarea primei etape, comparația all-to-all. Firele multiple pot procesa diferite aliniamente perechi simultan și independent, cu o mică pierdere de timp CPU.

În stadiul de aliniere progresivă (Feng și Doolittle, 1987 Thompson et al., 1994), calculele de aliniere de la grup la grup sunt efectuate împreună cu un arbore de ghidare. Acest proces nu este foarte potrivit pentru paralelizare, deoarece ordinea calculelor de aliniere este restricționată de arborele de ghidare. Adică, o aliniere la un nod nu poate fi efectuată până când toate aliniamentele din nodurile sale secundare nu au fost finalizate. Atâta timp cât această restricție este menținută, aliniamentele pot fi efectuate la nodurile copil care sunt independente unul de celălalt. Astfel, în implementarea noastră, eficiența paralelizării este inevitabil scăzută în această etapă. Deși este posibil să se proiecteze un arbore ghid care să fie potrivit pentru paralelizare (Li, 2003), noi nu am adoptat această abordare, deoarece în MAFFT această etapă consumă mai puțin timp CPU decât celelalte două (pentru detalii vezi Tabelul suplimentar, în care procentul de timp de execuție al acestei etape este sub 2%).

În fiecare pas al procesului de rafinare iterativă (Barton și Sternberg, 1987 Berger și Munson, 1991 Gotoh, 1993), un aliniament este împărțit în două sub-alinieri și apoi cele două sub-aliniamente sunt realiniate, conform strategiei iterative dependente de arbore ( Gotoh, 1996 Hirosawa et al., 1995), pentru a obține o aliniere cu un scor obiectiv mai mare. Am implementat cea mai bună abordare-prima și o abordare simplă de alpinism pentru această etapă.

În cea mai bună abordare, realinările sunt efectuate pentru toate cele 2 posibileN − 3 diviziuni pe arbore, apoi este selectată alinierea cu cel mai mare scor obiectiv, unde N este numărul de secvențe. Acest proces se repetă până când nu se găsește nicio aliniere cu un scor mai mare. Deoarece doar alinierea cu cel mai mare scor contribuie la pasul următor, iar celelalte aliniamente sunt eliminate, această abordare este evident ineficientă.

Ca alternativă, în care mai puține aliniamente sunt aruncate, am implementat o abordare simplă de alpinism. Procesele de realiniere sunt atribuite aleatoriu mai multor fire și efectuate în paralel. Dacă scorul unei noi alinieri de către un fir este mai bun decât alinierea inițială, atunci acesta înlocuiește instantaneu alinierea inițială. În consecință, poate exista un caz în care două sau mai multe fire diferite în paralel produc aliniamente diferite și mai bune. Într-un astfel de caz, prima aliniere (în termeni de timp) este selectată, în timp ce celelalte aliniamente sunt eliminate. Abordarea simplă de alpinism este de așteptat să fie eficientă atunci când numărul de fire este mic. Odată cu creșterea numărului de fire, numărul de aliniamente aruncate crește și astfel eficiența va scădea. Alinierea rezultată depinde de numere aleatorii.

Cea mai bună abordare primul oferă un rezultat stabil independent de numere aleatorii, în timp ce abordarea simplă de alpinism are în general un avantaj, în ceea ce privește viteza. Prin urmare, am examinat care este mai potrivit pentru problema de aliniere multiplă. Pentru a compara eficiența acestora, cea mai simplă opțiune de rafinare iterativă fără ponderare a secvenței a fost aplicată tuturor celor 218 aliniamente din BAliBASE versiunea 3 (Thompson et al., 2005). Abordarea simplă de alpinism a fost efectuată de 10 ori cu numere aleatorii diferite. Pentru fiecare dintre cele 218 × 10 alergări cu abordarea simplă de alpinism, scorul obiectivului final a fost comparat cu scorul obiectivului final obținut din abordarea cea mai bună, primul. Prima a fost mai mare decât cea din urmă în 972 de cazuri, în timp ce prima a fost mai mică decât cea din urmă în 917 cazuri. În restul de 291 de cazuri, cele două aliniamente au fost identice una cu cealaltă. Acest rezultat raționalizează utilizarea abordării simple de alpinism.

Pentru a confirma că acuratețea aliniamentelor prin cele două abordări nu se disting una de cealaltă și de cea generată de versiunea în serie, au fost calculate și scorurile de referință BAliBASE, unde diferențele față de aliniamentele de referință (presupuse a fi corecte) au fost evaluate ca scorurile SP și TC (Thompson et al., 1999). Scorurile medii generale SP ale uneia dintre cele mai precise opțiuni MAFFT, L-INS-i, au fost 0,8728 ± 0,0003649 (media simplă de alpinism ± SD), 0,8720 (cel mai bun primul) și 0,8722 (versiunea de serie) . Scorurile medii generale ale TC au fost 0,5926 ± 0,001162 (alpinism simplu), 0,5927 (cel mai bun primul) și 0,5928 (versiunea de serie). Media și SD-ul scorurilor abordării simple de alpinism au fost calculate din 10 alergări cu numere aleatorii diferite.

Figura 1 arată timpul real necesar pentru a calcula cea mai mare aliniere (BB30003 142 secvențe × 451 site-uri inclusiv goluri) în BAliBASE, folosind numere diferite (1�) de fire pe un PC cu 16 nuclee (4 × Quad-Core). procesor AMD Opteron 8378). Când numărul de fire este de opt, eficiența paralelizării este de 0,89 și 0,55 pentru cea mai bună abordare-prima și, respectiv, pentru abordarea simplă de alpinism. După cum era de așteptat, pierderea vitezei în abordarea simplă de alpinism crește odată cu creșterea numărului de fire. Acest lucru se datorează faptului că numărul de aliniamente aruncate crește, așa cum sa menționat mai sus. Pierderea de viteză pentru abordarea cea mai bună-prima este relativ mică. Cu toate acestea, în intervalul sistemelor țintă din prezentul studiu (PC-uri multi-core obișnuite), abordarea simplă de alpinism este mai rapidă și, prin urmare, a fost adoptată ca implicită.

Eficiența paralelizării pentru o opțiune de rafinare iterativă (L-INS-i) cu două strategii de paralelizare (cel mai bun primul și simplu alpinism) și o opțiune progresivă (L-INS-1). Liniile corespund situației ideale în care (Timp scurs cu n fire) = (Timp scurs cu un singur fir) / n. Argumentele liniei de comandă sunt: ​​Best-first, mafft-linsi --bestfirst --thread n intrare Simple hill-climbing, mafft-linsi --thread n intrare Progresiv, mafft-linsi --maxiterate 0 --thread n intrare

Am examinat, de asemenea, aplicabilitatea abordării simple de alpinism la date mai mari. După cum se arată în tabelul suplimentar, eficiența cu opt fire este de 0,55𠄰,74 pentru cinci seturi de date, fiecare cu secvențe de �.

Versiunile MAFFT 𢙖.8 trec la versiunea pthread prin simpla adăugare a --thread n argument, unde n este numărul de fire de folosit. Nu este necesară nicio configurație specială pentru procesarea paralelă pe un PC multi-core cu sistemul de operare Linux.


Alinierea secvențelor multiple

Alinierea secvenței multiple (MSA) este în general alinierea a trei sau mai multe secvențe biologice (proteine ​​sau acid nucleic) de lungime similară. Din rezultat, omologia poate fi dedusă și relațiile evolutive dintre secvențe studiate.

În contrast, Alinierea secvenței în perechi instrumentele sunt folosite pentru a identifica regiuni de similaritate care pot indica relații funcționale, structurale și/sau evolutive între două secvențe biologice.

Nou instrument MSA care folosește arbori de ghidare însămânțați și tehnici de profil HMM pentru a genera aliniamente. Potrivit pentru aliniamente medii-mari.

EMBOSS Cons creează o secvență consens dintr-o aliniere multiplă de proteine ​​sau nucleotide.

Instrument MSA foarte rapid, care se concentrează pe regiunile locale. Potrivit pentru aliniamente mari.

Instrument MSA care utilizează transformate rapide Fourier. Potrivit pentru aliniamente medii-mari.

Instrument MSA precis, mai ales bun cu proteine. Potrivit pentru aliniamente medii.

Transformați un rezultat al căutării de similaritate de secvență într-o aliniere a secvenței multiple sau reformatați o aliniere a secvenței multiple folosind programul MView.

Instrument MSA bazat pe consecvență care încearcă să atenueze capcanele metodelor de aliniere progresivă. Potrivit pentru aliniamente mici.

EBI are un nou program de aliniere a secvențelor multiple conștient de filogenie, care folosește informațiile evolutive pentru a ajuta la plasarea inserțiilor și ștergerilor.
Încercați-l la WebPRANK.

Vă rugăm să citiți documentația de ajutor și amp și întrebări frecvente furnizate înainte de a solicita ajutor de la personalul nostru de asistență. Dacă aveți feedback sau întâmpinați probleme, vă rugăm să ne anunțați prin intermediul asistenței EMBL-EBI. Dacă intenționați să utilizați aceste servicii în timpul unui curs, vă rugăm să ne contactați. Citiți Notificarea noastră de confidențialitate dacă vă preocupă confidențialitatea și modul în care gestionăm informațiile personale.

EMBL-EBI, Wellcome Trust Genome Campus, Hinxton, Cambridgeshire, CB10 1SD, Marea Britanie +44 (0)1223 49 44 44


Introducere

O gamă largă de analize moleculare se bazează pe aliniamente de secvențe multiple (MSA), de exemplu, detectarea motivelor în gene și genomuri [1], predicția structurilor tridimensionale [2], inferența filogenetică [3] și detectarea selecției pozitive [4]. În toate aceste studii, MSA inițial poate avea un impact puternic asupra concluziilor și interpretărilor biologice [5]. În consecință, MSA este o zonă bogat dezvoltată de bioinformatică și biologie computațională.

Secvențele de ADN care urmează să fie aliniate conțin adesea cadre de citire deschise (ORF) care codifică proteine. O secvență de codificare poate fi considerată fie la nivel de nucleotide (NT) fie la nivel de aminoacizi (AA). Din cauza redundanței codurilor genetice, codoni diferiți codifică același AA. Secvența NT este astfel mai puțin conservată, dar mai informativă decât traducerea sa AA. Deoarece sunt mai informative, secvențele NT ar trebui să poată oferi aliniamente la fel de bune sau chiar mai bune decât singura lor traducere AA. În special, alinierea secvențelor NT poate explica ORF-urile întrerupte. Aceste întreruperi rezultă din (i) inserarea unui non-multiplu de 3 nucleotide consecutive – sau ștergerea acestora –, ambele inducând deplasări de cadre care duc la translația secvenței AA aberante tranzitorii sau ireversibile în aval și (ii) înlocuirea unei secvențe în cadru. nucleotidă rezultând codoni stop prematuri neaștepți care scurtează secvența AA. Aceste evenimente pot avea cauze fie artefactuale, fie biologice. În primul rând, pot apărea erori experimentale. Erorile de secvențiere sunt frecvente cu noile tehnologii de secvențiere care au ca rezultat rate de eroare crescute în homopolimeri atunci când se utilizează 454 GS-FLX [6] și, pe scurt, citirea cu Analizorul genomului Illumina [7]. Acest fenomen este întărit atunci când ADN-ul degradat antic sau actual servește ca șablon PCR [8]. În al doilea rând, inactivarea genelor în cursul evoluției duce la pseudogene care prezintă întreruperi ale ORF-urilor lor originale și a căror identificare s-a dovedit dificilă din punct de vedere computațional [9]. În al treilea rând, mutațiile de deplasare a cadrelor programate care sunt tolerate în timpul translației au fost documentate pe scară largă [10] și a fost raportat rolul lor în evoluția funcției noi a genei [11] Pentru a obține o calitate mai mare a alinierii NT și a detecta întreruperile ORF, traducerea AA ar trebui să fie luate în considerare în timpul procesului de aliniere. Ignorarea acesteia ar însemna omiterea unor informații fundamentale. Cu toate acestea, deplasările de cadre și codonii de oprire prematură împiedică alinierea corectă ghidată de AA a secvențelor NT.

Numerous tools exist to align DNA sequences, among which are CLUSTAL [12], T-COFFEE [13], DIALIGN [14], MUSCLE [15], MAFFT [16], and the more recently proposed PRANK [3] and FSA [17]. However, when dealing with protein-coding sequences, these methods do not take into account the corresponding AA translations. Ignoring the AA translation is a major handicap in these methods for two main reasons [18], [19]: (i) as NT sequences are less conserved, clear similarities at the AA level can be obscured at the NT level thus complicating the alignment (ii) current optimization criteria during the alignment procedure do not penalize insertion/deletion events (indels) that create translation frameshifts. As a result, a protein-coding sequence containing an insertion of two nucleotides followed by a downstream insertion of 7 nucleotides will have the same gap-related penalties as the more realistic scenario of an insertion of three nucleotides followed by another insertion of 6.

To overcome these problems, one common strategy consists of using a three-step approach. First of all coding NT sequences are translated into AA, these AA sequences are then aligned, and lastly, the obtained protein alignment is used for deriving the NT one. Tools such as revTrans [18], transAlign [19], PAL2NAL [20], and TranslatorX [21] were specifically developed to automate this straightforward alignment strategy. Note that PAL2NAL additionally allows to manually specify a priori the position of known frameshifts. DIALIGN [14] proposes this three-step strategy as an option for aligning DNA sequences. Moreover, it can either consider the full DNA sequence as coding, or search for its longest reading frame. The main drawback of this three-step approach is its inability to handle unexpected frameshifting substitutions. The AA translation that follows such events is no longer the correct one. At best, this erroneous translation will quickly lead to a stop codon that will alert the user and/or prevent the AA alignment. In other cases, the translated AA sequence will look like a highly divergent, orphan sequence at the protein level and will induce a partly aberrant DNA alignment. Such cases seem to be frequently encountered even in benchmark alignment datasets [22].

Unlike the vast literature on sequence alignment, few studies have focused on AA-aware NT sequence alignment. One of the first works on this subject was by Hein [23]. The author proposed a general DNA/protein model, where the cost of an alignment is a combination of its cost at the NT and AA levels. He then considered a special case where the two costs are simply summed and sequence evolution is idealized to involve only nucleotide substitutions and AA indels (no frameshift is allowed). An algorithm has been proposed to align two sequences of length and under this model [23]. A solution was then described to solve the same problem under affine gap costs in by Arvestad [24] and Pedersen et al. [25]. These improvements seemed to be promising as this algorithm reached the same asymptotic complexity as classical DNA alignment methods. However, the authors acknowledged that the constant factor masked by the notation may be limitative in practice [25]. Indeed, to obtain a pairwise alignment, their method needs to compute table entries which preclude its use in the MSA context.

An alternative approach that was recently proposed [26] consists of scoring the alignment according to a weighted sum of four costs: the NT alignment cost plus those of its three possible AA alignment translations. To make the algorithm simpler and faster, no specific cost is associated with indels that induce frameshifts. Here, frameshifting indels are supposed to be penalized by the AA mismatch they will induce. Considering all three reading frames may appear surprising since often only one is relevant, but this tool was specifically developed for handling viral genomes which may use overlapping reading frames [26].

In a slightly different context, an algorithm has been proposed to detect frameshift errors in newly determined NT sequences by comparison with AA sequences in public databases [27]. The algorithm generalizes the classical Smith-Waterman pairwise algorithm [28] so that the three reading frames are considered. An explicit frameshift cost is used to penalize frameshifts. This method provides an elegant solution for evaluating sequence proximity but cannot be extended to MSA since the underlying alignment cannot be displayed by the classical matrix representation used in MSA algorithms.

Here we present an AA-aware alignment algorithm where both input NT sequences could contain multiple frameshifts and/or stop codons. This pairwise coding sequence alignment method is fast enough to be extended to a MSA program called MACSE (Multiple Alignment of Coding SEquences). Indeed although pairwise solutions have existed for almost two decades, MACSE is the first MSA program able to align coding sequences based on their AA translations while accounting for frameshifts. We illustrate the relevance and usefulness of the MACSE program on biological case studies aimed at 1) computing MSA of protein-coding genes containing non-functional, pseudogene sequences, 2) aligning high-throughput sequencing reads against reference coding sequences and 3) detecting undocumented frameshifts in published sequences. MACSE is an efficient solution to detect errors in coding sequences and the first automatic solution to align pseudogenes while taking into account their potential AA translation and preserving their codon structure.


An Overview of Multiple Sequence Alignments and Cloud Computing in Bioinformatics

Multiple sequence alignment (MSA) of DNA, RNA, and protein sequences is one of the most essential techniques in the fields of molecular biology, computational biology, and bioinformatics. Next-generation sequencing technologies are changing the biology landscape, flooding the databases with massive amounts of raw sequence data. MSA de seturi de date secvențe în continuă creștere devine un blocaj semnificativ. In order to realise the promise of MSA for large-scale sequence data sets, it is necessary for existing MSA algorithms to be run in a parallelised fashion with the sequence data distributed over a computing cluster or server farm. Prin urmare, combinarea algoritmilor MSA cu tehnologiile cloud computing va îmbunătăți viteza, calitatea și capacitatea MSA de a gestiona un număr mare de secvențe. În această revizuire, sunt discutate mai multe alinieri de secvențe, cu un accent special pe algoritmii ClustalW și Clustal Omega. Cloud computing technologies and concepts are outlined, and the next generation of cloud base MSA algorithms is introduced.

1. Introducere

Alinierea secvenței multiple (MSA) este o procedură de calcul esențială și utilizată pe scară largă pentru analiza secvenței biologice în biologia moleculară, biologia computațională și bioinformatică. MSA are completed where homologous sequences are compared in order to perform phylogenetic reconstruction, protein secondary and tertiary structure analysis, and protein function prediction analysis [1]. Aliniamentele biologice bune și precise pot avea o semnificație semnificativă, arătând relații și omologie între diferite secvențe și pot oferi informații utile, care pot fi utilizate pentru a identifica în continuare noi membri ai familiilor de proteine. The accuracy of MSA is of critical importance due to the fact that many bioinformatics techniques and procedures are dependent on MSA results [1].

Datorită semnificației MSA, au fost dezvoltați mulți algoritmi MSA. Unfortunately, constructing accurate multiple sequence alignments is a computationally intense and biologically complex task, and as such, no current MSA tool is likely to generate a biologically perfect result. Prin urmare, acest domeniu de cercetare este foarte activ, urmărindu-se dezvoltarea unei metode care să poată alinia mii de secvențe lungi și să producă aliniamente de înaltă calitate și într-un timp rezonabil [2, 3]. Alignment speed and computational complexity are negatively affected when the number of sequences to be aligned increases. Progresele recente în tehnologiile de secvențiere cu randament ridicat înseamnă că această ieșire a secvenței crește într-un ritm exponențial, biologia, peisajul fiind punctat de o serie de proiecte la scară largă, cum ar fi Human Genome Project [4], 1000 Genomes Project [5] și Proiectul Genome 10K [6]. Într-adevăr, tehnologii precum Roche/454 [7], Ilumina [8] și SOLiD [9] sunt capabile să producă perechi de bază Giga (Gbp) per mașină pe zi [10]. The entire worldwide second-generation sequencing capacity surpasses 13 Pbp per year (recorded in 2011) and is continuing to increase yearly by a factor of five [11]. Alte date la scară largă apar din tehnologiile de mare capacitate, cum ar fi seturi de date privind expresia genelor, structurile 3D de proteine, interacțiunea proteină-proteină și altele, care generează, de asemenea, seturi uriașe de date secvențe. The analysis and storage of the growing genomic data represents the central challenge in computational biology today.

As the protein alignment problem has been studied for several decades, studies have shown considerable progress in improving the accuracy, quality, and speed of multiple alignment tools, with manually refined alignments continuing to provide superior performance to automated algorithms. However, more than three sequences of biologically relevant length can be difficult and time consuming to align manually therefore, computational algorithms are used as a matter of course [2]. Secvențele pot fi aliniate folosind întreaga lor lungime (alinierea globală) sau la anumite regiuni (alinierea locală). Multiple sequence alignment for protein sequences is much more difficult than the DNA sequence equivalent (containing only 4 nucleotides) due to the fact that there are 20 different amino acids. Global optimization techniques, developed in applied mathematics and operations research, provide a generic toolbox for solving complex optimization problems. Optimizarea globală este acum utilizată zilnic, iar aplicarea ei la problema MSA a devenit o rutină [12]. Local alignments are preferable however, they can be challenging to calculate due to the difficulty associated with the identification of sequence regions of similarity. The two major aspects of importance for MSA tools for the user are biological accuracy and the computational complexity. Biological accuracy concerns how close the multiple alignments are to the true alignment and are the sequences aligning correctly, showing insertions, deletions, or gaps in the right positions. Computational complexity refers to the time, memory, and CPU requirements. Complexity is of increasing relevance as a result of the increasing number of sequences needed to be aligned. Complexitatea instrumentelor MSA primare a fost întotdeauna

, unde este complexitatea, este lungimea secvenței și este numărul de secvențe care trebuie aliniate. Până de curând, aceasta nu a fost o problemă, deoarece a fost întotdeauna mai mică decât, prin urmare, majoritatea algoritmilor se concentrau pe modul de a trata secvențele lungi mai degrabă decât numărul de secvențe, iar acum situația s-a schimbat, în care o mulțime de aliniamente au mai mari decât, prin urmare, noi. iar algoritmii MSA mai recenti se concentrează nu numai pe lungimea secvențelor, ci și pe numărul tot mai mare de secvențe [13].

O gamă largă de algoritmi de calcul au fost aplicați problemei MSA, inclusiv metode lente, dar precise, cum ar fi programarea dinamică și metode euristice sau probabilistice mai rapide, dar mai puțin precise. Dynamic programming (DP) is a mathematical and computational method which refers to simplifying a complicated problem by subdividing it into smaller and simpler components in a repeated manner. Tehnica de programare dinamică poate fi aplicată la aliniamente globale folosind metode precum algoritmul Needleman-Wunsch [14] și aliniamente locale folosind algoritmul Smith-Waterman [15]. Până la mijlocul anilor 1980, algoritmii tradiționali de aliniere a secvențelor multiple erau cel mai bine potriviți doar pentru două secvențe, așa că atunci când era vorba de producerea alinierii secvențelor multiple cu mai mult de două secvențe, s-a constatat că completarea manuală a alinierii a fost mai rapidă decât utilizarea dinamică tradițională. algoritmi de programare [16]. Algoritmii de programare dinamică sunt utilizați pentru calcularea aliniamentelor pe perechi (două aliniamente secvențe) cu complexitatea de timp de . În teorie, această metodă ar putea fi extinsă la mai mult de două secvențe, totuși, în practică, este prea complexă, deoarece complexitatea în timp și spațiu devine foarte mare [17]. Prin urmare, producerea alinierii secvențelor multiple necesită utilizarea unor metode mai sofisticate decât cele utilizate în producerea unei alinieri pe perechi, deoarece este mult mai complex din punct de vedere computațional. Finding a mathematically optimal multiple alignment of a set of sequences can generally be defined as a complex optimization problem or NP-complete problem as it must identify an MSA with the highest score from the entire set of alignments therefore, heuristic (“best guess”) methods must be used.

2. Multiple Sequence Alignment Algorithms

The most popular heuristic used from which the majority of multiple sequence alignments are generated is that developed by Feng and Doolittle [18], which they referred to as “progressive alignment” [16, 18]. Progressive alignment works by building the full alignment progressively, firstly completing pairwise alignments using methods such as the Needleman-Wunsch algorithm, Smith-Waterman algorithm, k-tuple algorithm [19], or k-mer algorithm [20], and then the sequences are clustered together to show the relationship between them using methods such as mBed and k-means [21]. Similarity scores are normally converted to distance scores and guide trees are constructed using these scores by guide tree building methods such as Neighbour-Joining (NJ) [22] and Unweighted Pair Group Method with Arithmetic Mean UPGMA [23]. Once the guide tree is built, the multiple sequence alignment is assembled by adding sequences to the alignment one by one according to the guide tree, that is, the most similar sequences added first and then gradually adding more distant sequences. Unfortunately, this heuristic has a greedy nature that is, it only looks at two sequences at a time and ignores the remaining data and therefore cannot guarantee an optimal solution. Also, if mistakes are made in the initial stages of the alignment, they cannot be fixed in later stages, and the mistake will continue throughout the alignment process with the problem worsening as the number of sequences increases. Progressive alignment is the foundation procedure of several popular alignment algorithms such as ClustalW [24], Clustal Omega [21], MAFFT [25], Kalign [26], Probalign [27], MUSCLE [13], DIALIGN [28], PRANK [29], FSA [30], T-Coffee [31, 32], ProbCons [33],and MSAProbs [34]. Different methods for producing multiple sequence alignment exist, and their use depends on user preferences and sequence length and type, as shown in Table 1.

An improved version of the progressive alignment method was developed called “iterative progressive algorithms.” These algorithms work in a similar manner to progressive alignment however, this approach repeatedly applies dynamic programming to realign the initial sequences in order to improve their overall alignment quality, also at the same time adding new sequences to the growing MSA. The iteration benefits the alignment by correcting any errors produced initially, therefore improving the overall accuracy of the alignment [35]. Iterative methods are able to give 5%–10% more accurate alignments however, they are limited to alignments of a few hundred sequences only [21]. The most used iterative alignment algorithms include PRRP [36], MUSCLE [13], Dialign [28], SAGA [37], and T-COFFEE [32, 38].

Multiple sequence alignments can also be constructed by using already existing protein structural information. It is believed that by incorporating structural information to the alignment, the final MSA accuracy can be increased therefore, most structure-based MSA are of higher quality than those based on sequence alignment only. The reason for structure-based MSA being of better quality is not due to a better algorithm but rather an effect of structures evolutionary stability that is, structures evolve more slowly than sequences [39]. The most popular structure and based MSA is 3D-COFFEE [40], and others include EXPRESSO [41] and MICAlign [42].

Motif discovery algorithms are another type of MSA algorithms that are used. These methods are used to find motifs in the long sequences this process is viewed as a “needle in a haystack” problem, due to the fact that the algorithm looks for a short stretch of amino acids (motif) in the long sequence. One of the most widely used tools for searching for motifs is PHI-Blast [43] and Gapped Local Alignments of Motifs (GLAM2) [44].

Short sequence alignment algorithms are also beginning to emerge, primarily due to advances in sequencing technologies. Most genomic sequence projects use short read alignment algorithms such as Maq [45], SOAP [46], and the very fast Bowtie [47] algorithms.

3. Top Multiple Sequence Alignment Algorithms

The number of multiple sequence alignment algorithms is increasing on almost monthly bases with

1-2 new algorithms published per month. The computational complexity and accuracy of alignments are constantly being improved however, there is no biologically perfect solution as yet. ClustalW (one of the first members of the Clustal family after ClustalV) is probably the most popular multiple sequence alignment algorithm, being incorporated into a number of so-called black box commercially available bioinformatics packages such DNASTAR, while the recently developed Clustal Omega algorithm is the most accurate and most scalable MSA algorithms currently available. ClustalW and Clustal Omega are described later, and also a brief description is provided for the T-Coffee, Kalign, Mafft, and MUSCLE multiple sequence alignment algorithms.

3.1. ClustalW

ClustalW [24] was introduced by Thompson et al. in 1994 and quickly became the method of choice for producing multiple sequence alignments as it presented a dramatic increase in alignment quality, sensitivity, and speed in comparison with other algorithms. ClustalW incorporates a novel position-specific scoring scheme and a weighting scheme for downweighting overrepresented sequence groups, with the

” representing “weights.” Firstly, the algorithm performs a pairwise alignment of all the sequences (nucleotide or amino acid) using the k-tuple method by Wilbur and Lipman [19] which is a fast, albeit approximate, method or the Needleman-Wunsch method [14] which is known as the full dynamic programming method. These methods calculate a matrix which shows the similarity of each pair of sequences. The similarity scores are converted to distance scores, and then the algorithm uses the distance scores to produce a guide tree, using the Neighbour-Joining (NJ) method [22] for guide tree construction. The last step of the algorithm is the construction of the multiple sequence alignment of all the sequences. The MSA is constructed by progressively aligning the most closely related sequences according to the guide tree previously produced by the NJ method (see Figure 1 for an overview).


ClustalW algorithm, which works by taking an input of amino acid or nucleic acid sequences, completing a pairwise alignment using the k-tuple method, guide tree construction using the Neighbour-Joining method, followed by a progressive alignment to output a multiple sequence alignment.
3.1.1. Pairwise Alignment

The k-tuple method [19], a fast heuristic “best guess” method, is used for pairwise alignment of all possible sequence pairs. This method is specifically used when the number of sequences to be aligned is large. The similarity scores are calculated as the number of k-tuple matches (which are runs of identical residues, usually 1 or 2 for protein residues or 2–4 for nucleotide sequences) in the alignment between a pair of sequences. Similarity score is calculated by dividing the number of matches by the sum of all paired residues of the two compared sequences. Fixed penalties for every gap are subtracted from the similarity score with the similarity scores later converted to a distance score by dividing the similarity score by 100 and subtracting it from 1.0 to provide the number of differences per site.

Then, all of the k-tuples between the 2 sequences are located using a hash table. A dot matrix plot between the two sequences is produced with each k-tuple match represented as a dot. The diagonals with the most matches in the plot are found and marked within a selected “Window Size” of each top diagonal. This sets the most likely region for similarity between the two sequences to occur. The last stage of the k-tuple method is to find the full arrangement of all k-tuple matches by producing an optimal alignment similar to the Needleman-Wunsch method but only using k-tuple matches in the set window size, which gives the highest score. The score is calculated as the number of exactly matching residues in the alignment minus a “gap penalty” for every gap that was introduced.

3.1.2. Guide Tree Construction

ClustalW produces a guide tree according to the “Neighbor-Joining” method. The NJ method is often referred to as the star decomposition method [48]. The NJ method keeps track of nodes on a tree rather than a taxa (a taxonomic category or group, such as phylum, order, family, genus, or species) or clusters of taxa. The similarity scores are used from the previous k-tuple method and stored in a matrix. A modified distance matrix is constructed in which the separation between each pair of nodes is adjusted by calculating an average value for divergence from all other nodes. The tree is then built by linking the least distant pair of nodes. When two nodes are linked, their common ancestral node is added to the tree and the terminal nodes with their respective branches are removed from the tree. This process allows the conversion of the newly added common ancestor into a terminal node tree of reduced size. At each stage in the process, two terminal nodes are replaced by one new node. The process is completed when two nodes remain separated by a single branch. The tree produced by the NJ method is un-rooted and its branch lengths are proportional to divergence along each branch. The root is placed at the position at which it can make the equal branch length on either side of the root. The guide tree is then used to calculate weight for each sequence, which depends on the distance from branch to the root. If a sequence shares a common branch with another sequence, then the two or more sequences will share the weight calculated from the shared branch, and the sequence lengths will be added together and divided by the number of sequences sharing the same branch.

3.1.3. Progressive Alignment

ClustalW’s progressive alignment uses a series of pairwise alignments to align sequences by following the branching order of the guide tree previously constructed by the NJ method. The procedure starts at the tips of the rooted tree proceeding towards the root. At each step, a full dynamic programming algorithm is used with a residue weight matrix (BLOSUM) and penalties for opening and extending gaps.

3.2. Clustal Omega

Clustal Omega is the latest MSA algorithm from the Clustal family. This algorithm is used to align protein sequences only (though nucleotide sequences are likely to be introduced in time). The accuracy of Clustal Omega on small numbers of sequences is similar to other high-quality aligners however, on large sequence sets, Clustal Omega outperforms other MSA algorithms in terms of completion time and overall alignment quality. Clustal Omega is capable of aligning 190,000 sequences on a single processor in a few hours [21]. The Clustal Omega algorithm produces a multiple sequence alignment by firstly producing pairwise alignments using the k-tuple method. Then, the sequences are clustered using the mBed method. This is followed by the k-means clustering method. The guide tree is next constructed using the UPGMA method. Finally, the multiple sequence alignment is produced using the HHalign package, which aligns two profile hidden Markov models (HMM) as shown in Figure 2.


Multiple sequence alignment using HMM and simulated annealing

Can anyone help me with Multiple Sequence Alignment (MSA) using Hidden Markov Model (HMM) by giving an example or a reference except these 2 references:

I know that there are 3 states: match, deletion and insertion and I know the emission probabilities and transitions probabilities can be learned by viterbi algorithm but what is vague is that if I want to do multiple alignment I need to have HMM and if I want to have HMM I need to have aligned sequences but we know that sequences are unaligned and also with simulated annealing we can Enter randomness to the model and have better solutions and also this algorithm is different with E-M algorithm and I have another question how many states our model of HMM for this problem should have at the first step, does the number of states change during the time of convergence or it is fixed from the first??

If anybody can help me to understand what really happens in this MSA with HMM I'll appreciate.

I should explain that there have been found more sequences of DNA,RNA and protein but there are less information about structures and functions of each protein so we do MSA to understand the similarities between sequences and find out whether they are homologous (have a same ancestor) or not and find out the unknown structure and functions of sequences.


Priveste filmarea: Multiple Sequence Alignment (Ianuarie 2022).