De bepaling van de homologe gebieden van moleculaire sequenties wordt vaak gebruikt voor de verdere gevolgtrekking van hun functie en evolutie, en dus nauwkeurig multiple sequence alignment (MSA) van nucleïnezuren en eiwit-sequenties is van cruciaal belang., Bijgevolg is er enorme inspanning geleverd in de ontwikkeling en implementatie van verschillende MSA-algoritmen, waarbij verschillende benaderingen worden gebruikt om de resulterende uitlijnnauwkeurigheid te verbeteren.

De nauwkeurigheidsbeoordeling van MSA-programma ‘ s wordt vaak gedaan door handmatig (of semi-automatisch) samengestelde sequentiedatabases zoals BAliBASE , PREFAB en SABmark te gebruiken . Tot nu toe is BAliBASE de meest gebruikte uitlijningsdatabase geweest bij het evalueren van de prestaties van verschillende MSA-programma ‘ s. Het werd geconstrueerd gebruikend eiwitopeenvolgingen of modellen met bekende driedimensionale structuren., De laatste creatie, Versie 3.0, had een toename van het aantal beschikbare sequenties en uitlijningen. Deze verbeteringen hebben blijkbaar tegemoet gekomen aan de grote zorgen van Karplus en Hu met betrekking tot het gebruik van BAliBASE om MSA-algoritmen te benchmarken.

Alignment databases bieden een bron van nauwkeurige alignments om de nauwkeurigheid en snelheid van verschillende programma ‘ s te meten, maar ze hebben ook een aantal nadelen. Ook al worden de gegevensbanken handmatig op elkaar afgestemd, toch bestaat er nog steeds de mogelijkheid van een verkeerde afstemming die tot problemen bij de beoordeling van de nauwkeurigheid zou leiden., De reeksen alignments blijven nog vrij klein en kunnen niet de volledige waaier van scenario ‘ s van eiwitevolutie vertegenwoordigen. Bovendien is een groot nadeel van het gebruik van alignment databases dat algoritmen potentieel kunnen worden ontwikkeld en afgestemd op de alignments die alleen aanwezig zijn in deze datasets.

recentelijk zijn er verschillende DNA sequentie simulatie pakketten die indels bevatten, zoals MySSP en DAWG . MySSP is wijd gebruikt in verschillende studies van phylogenetic gevolgtrekking en evolutionaire afstandschatting gekoppeld aan de nauwkeurigheid van de aanpassing van DNA ., Voor eiwitten, Lassmann en Sonnhammer in een eerdere vergelijking van MSA algoritmen gebruikt kunstmatig gecreëerde sequentie sets gegenereerd door het simulatieprogramma Rose . De roos simuleert opeenvolgingen van proteã nen die voor het voorkomen van indels toestaan. Datasets gegenereerd door Rose presenteren hun eigen beperkingen voor de studie van de uitlijnnauwkeurigheid. In Nam, vertegenwoordigen de grootte en het aantal van indel niet voldoende empirische gegevens voor proteã nen die voor verschillende evolutionaire tijden zijn uiteengelopen. Ook gaat het programma uit van gelijke evolutionaire tarieven van alle plaatsen in het eiwit.,

in deze studie introduceren we een verbeterde benadering om de nauwkeurigheid van de uitlijning te beoordelen door gebruik te maken van gesimuleerde eiwitsequenties gegenereerd door Simprot . Simprot is een geavanceerd simulatieprogramma dat gebruik maakt van een geparametreerde versie van de Qian en Goldstein insertion and deletion (indel) distributie. Hoewel de originele distributie empirisch werd afgeleid uit een subset van alignments van sterk diverged eiwitopeenvolgingen, laat de geparametreerde versie een zeer flexibele simulatie van indels in opeenvolgingen voor alle niveaus van opeenvolgingsafwijking toe., Simprot maakt ook variabele substitutie en indel tarieven op verschillende locaties door het implementeren van gamma gedistribueerde sites tarieven . Drie modellen van aminozuren substitutie (PMB, PAM en JTT) zijn ook beschikbaar. We hebben Simprot gebruikt om bekende alignments met een breed scala aan evolutionaire parameters te genereren, evenals de nieuwste balibase-database van samengestelde alignments, om de nauwkeurigheid en snelheid van populaire en publiek beschikbare proteïne multiple sequence alignment software programma ‘ s te onderzoeken.,

Uitlijningsprogramma ‘s

Er zijn veel beschikbare computerpakketten die MSA’ s van eiwitsequenties genereren. We selecteerden negen van de momenteel meest gebruikte programma ‘ s (in volgorde van Publicatiedatum): Clustal W, Dialign2.2, T-Coffee, POA, Muscle, Mafft, ProbCons, Dialign-T en Kalign.

Clustal W versie 1.8

Dit is waarschijnlijk het meest gebruikte uitlijningsprogramma en het oudste van de geteste pakketten. De software voert een progressieve uitlijning uit, eerst gebruikmakend van een paarsgewijze sequentievergelijking door het berekenen van een afstandsmatrix die sequentiedivergentie opslaat., Nadat deze matrix is verkregen, wordt een tree guide gebouwd met behulp van Neighbor Joining, gevolgd door de derde en laatste stap waar sequenties worden uitgelijnd volgens de branch volgorde in de guide tree. Het programma maakt gebruik van twee gap penalty ‘ s in zijn alignment procedure: gap opening en gap uitbreiding, en in het geval van polypeptiden, een volledige aminozuur scoren gewicht matrix. Deze gap penalty ‘ s zijn voornamelijk afhankelijk van factoren zoals de gewichtsmatrix, sequentielengte en gelijkenis., In eenvoudige gevallen kan Clustale W nauwkeurig overeenkomstige domeinen en sequenties van bekende secundaire of tertiaire structuur uitlijnen, terwijl het in meer complexe gevallen kan worden gebruikt als een goed uitgangspunt voor verdere verfijning.

Dialign2. 2 Versie 2.2.1

Dit programma gebruikt een diagonale methode om sequenties lokaal en globaal uit te lijnen. Dialign2. 2 vergelijkt geen enkele residu, maar hele ononderbroken (geen hiaten, mismatches toegestaan) rek van residu ‘ s die diagonalen zouden vormen in een dot-matrix vergelijking van twee sequenties., Bijgevolg is het niet nadelig voor het invoegen en uitbreiden van gaten, en kan ongerelateerde segmenten ongewijzigd te laten. De eerste stap in de procedure creëert alle mogelijke paarsgewijze uitlijningen, waarbij een verzameling diagonalen wordt opgeslagen die voldoen aan bepaalde consistentiecriteria zonder conflicterende dubbele of cross-overtoewijzingen van residuen . Alle opgeslagen diagonalen worden gewogen om items met maximale som van gewichten te definiëren, en vervolgens gesorteerd om de mate van overlapping te bepalen, met nadruk op het bestaan van diagonalen aanwezig in meerdere sequenties., Een hebzuchtig-achtige algoritme doet een laatste verwerking, het controleren van diagonalen scores van boven naar beneden het creëren van een laatste meerdere uitlijning. Hiaten worden ingevoegd aan het einde van de MSA-creatie totdat alle aanwezige residuen zijn verbonden.

t-Coffee (Tree-based consistence objective function for alignment evaluation) versie 3.27

T-Coffee maakt gebruik van een progressieve strategie bij het uitlijnen van sequenties. Het programma maakt eerst een bibliotheek van twee verschillende bronnen: global alignments van Clustal W en local alignments van Lalign ., Voor elk paar reeksen worden globale alignments en de paarsgewijs lokale alignments gemaakt uit de tien top-scoring niet-kruisende segmenten. Het programma verwerkt de globale en lokale informatie, waarbij gewichten worden toegewezen aan alle pairwise alignments ten opzichte van sequence identity . Dit wordt gevolgd door de combinatie van groepen die worden samengevoegd in een enkele bibliotheek. Er is een uitbreidingsfase voor deze gecombineerde bibliotheek, waardoor het uiteindelijke gewicht van elk paar residuen een deel van de informatie in de hele bibliotheek weergeeft., Een laatste stap vereist een berekening van een afstandsmatrix en een buur die zich bij de boom aansluit, aangezien de uitlijning wordt gegenereerd met een progressieve strategie door de twee dichtste sequenties op de boom uit te lijnen volgens het gewicht dat is opgeslagen in de uitgebreide bibliotheek. Het initiële paar wordt dan gefixeerd en eventuele bestaande hiaten kunnen niet later worden verschoven. De progressieve uitlijning gaat door totdat elke reeks is uitgelijnd.

POA (Partial Order Alignment) versie 2.0

POA is een ander MSA-pakket dat een progressief uitlijningsalgoritme gebruikt zonder gegeneraliseerde profielen te gebruiken., Dit programma introduceert het gebruik van een Partial Order-Multiple Sequence Alignment (PO-MSA) formaat om sequenties weer te geven, en nauwkeuriger biologische inhoud weer te geven. Dit formaat slaat de uitlijning op als een gecomprimeerde grafiek voor minimale knooppunten en randtellingen, die nog steeds alle informatie bevat die beschikbaar is in een traditionele MSA. De opeenvolgingen worden opgeslagen als een lineaire reeks knopen die elk door twee randen worden verbonden. POA maakt gebruik van een traditioneel dynamisch programmeeralgoritme , waarbij lineaire sequenties worden vervangen door partiële orde (PO) grafieken., Deze po-structuren worden getransformeerd in gebruikelijke 2D-matrices en elke combinatie van cellen wordt achterwaarts gescoord zoals in een traditionele Smith-Waterman sequentieuitlijningprocedure . Deze matrices worden dan uitgebreid in elke richting (diagonaal, horizontaal, verticaal) waardoor de productie van de paarsgewijze uitlijning op knooppunten. MSA wordt verkregen uit de uitlijning van twee opeenvolgingen aan het begin met de toevoeging van andere opeenvolgingen achtereenvolgens aan het aanvankelijke paar.

Muscle (Multiple sequence comparison by log-expectation) versie 3.,6

spier maakt gebruik van een paarsgewijze profieluitlijning. Het programma bouwt eerst een progressieve uitlijning die vervolgens wordt verbeterd en verfijnd in twee volgende fasen. De progressieve uitlijning wordt gemaakt na de sequentie gelijkenissen, een afstand schatting en een UPGMA boom worden berekend. Muscle gebruikt twee afstandsmaten: een k mer-afstand voor niet-gebonden sequentieparen en een Kimura-afstand voor uitgelijnde paren . De progressieve alignment improvement fase creëert een nieuwe boom met de reeds berekende Kimura afstand matrix en bouwt vervolgens een betere alignment op basis van deze verbeterde boom., De laatste fase van verfijning maakt gebruik van een variant van de boomafhankelijke beperkte partitionering . Deze methode verwijdert een van de boomranden, bi-partitioneert de uitlijning en extraheert de profielen van beide partities die vervolgens opnieuw worden uitgelijnd met een Profiel-Profiel uitlijning. Elke tree edge wordt iteratief bezocht en de uitlijning met een bijgewerkte samengevatte paarsgewijze score van elk sequentiepaar wordt behouden. De randen worden bezocht in volgorde van afnemende afstand van de wortel, met een herschikking van individuele opeenvolgingen, die zich naar meer nauw verwante groepen van opeenvolgingen bewegen .,

Maffft (Multiple sequence alignment based on Fast Fourier Transform) versie 5.732

Maffft is een programma dat kan worden gebruikt met verschillende uitlijning benaderingen, ofwel progressieve uitlijning alleen (met Fast Fourier Transform), of progressieve gevolgd door iteratieve verfijning. Maffts basic run kan maximaal drie stappen hebben, maar de standaard procedure voert de eerste twee stappen uit. Ten eerste wordt een progressieve uitlijning gemaakt op basis van een ruwe afstand tussen elk sequentiepaar op basis van gedeelde 6-tupels., Een guide tree wordt ook gegenereerd door UPGMA met gewijzigde koppeling en sequenties worden dan uitgelijnd volgens de branch volgorde van de boom (deze stap alleen al wordt strategie FFT-NS-1 genoemd). De tweede stap herberekent een afstandsmatrix, gebaseerd op de informatie verzameld over de vorige stap, en de progressieve uitlijning wordt opnieuw gedaan met behulp van een boom verkregen uit de nieuwe matrix als uitgangspunt (tot deze stap, de strategie is bekend als FFT-NS-2 en het is de standaard gebruikt door de software)., De laatste fase is de iteratieve verfijning die de gewogen som van paren (WSP) score van de Gotoh optimaliseert, met een groep-naar-Groep uitlijning en de boomafhankelijke restrictie partitie techniek . Als alle drie stappen worden gebruikt, wordt de procedure FFT-NS-i genoemd, betekenend gebruikt het een FFT methode om homologe gebieden snel huidig in de opeenvolgingen te identificeren die door een iteratieve fase van verfijning wordt gevolgd., FFT zet elk enkel aminozuur huidig in een opeenvolging om in een vector die volume en polariteit vertegenwoordigt, die belangrijke factoren op substitutiegebeurtenissen zijn, toestaand de software om dergelijke gebeurtenissen met precisie te voorspellen.

Maffft bevat ook drie extra verfijningsalgoritmen: L-INS-i, G-ins-i en E-ins-i . Deze strategieën verhogen het aantal stappen dat nodig is om een MSA-afstemming tot vijf te maken. In deze gevallen vereist de eerste stap ook de bouw van een afstand matrix, niet met behulp van 6-tupels., Anders dan de FFT-NS – * benaderingen is er geen reconstructie van de berekende upgma boom en het programma gaat naar de tweede stap, het verdelen van de gap-vrije segmenten en het opslaan van score arrays voor elk gap-vrije segment van de ene reeks naar de andere. Mafft berekent vervolgens een” belang ” waarde uit de score van het segment en slaat op hoe vaak residuen verschijnen op andere segmenten., Alle “belang” waarden worden vervolgens verzameld in een” belang ” matrix in Stap drie die snel wordt gevolgd door een groep-tot-groep Uitlijning verkregen uit de score matrices en een wegingsschema op basis van een Needleman-Wunsch algoritme. Een laatste stap verfijnt iteratief de verkregen uitlijningen, het optimaliseren van een WSP score en de “belang” waarden eerder berekend.

ProbCons (Probabilistic consistence-based multiple sequence alignment) Versie 1.1

ProbCons is het enige programma dat een probabilistic consistentiemethode voor alignment gebruikt., Het is een wijziging van het traditionele sum-of-pairs scoringssysteem en bevat bovendien een pair-hidden Markov-model-gebaseerd progressive alignment algoritme. De uitlijningsprocedure is verdeeld in vier stappen, beginnend met een berekening van posterieure-waarschijnlijkheidsmatrices voor elk paar sequenties. Dit wordt gevolgd door een dynamische programmering berekening van de verwachte nauwkeurigheid van elke paarsgewijze uitlijning. Probabilistische consistentie transformatie wordt vervolgens gebruikt om de match nauwkeurigheid scores opnieuw te schatten., Een guide tree wordt berekend met hiërarchische clustering met de gelijkenis gedefinieerd door een gewogen gemiddelde van waarden tussen sequenties van elke cluster. De guide tree wordt gebruikt om de sequenties uit te lijnen met behulp van een progressieve aanpak. Een post-processing fase wordt ook gedaan, waar willekeurige bi-partities van de gegenereerde uitlijning opnieuw worden uitgelijnd om te controleren op betere uitlijningsgebieden. ProbCons verschilt van andere uitlijningsprogramma ‘ s omdat het geen biologische concepten zoals positie-specifieke gap scoring, evolutionaire boomconstructie en andere functies die vaak worden gebruikt door andere pakketten omvat.,

Dialign-T versie 0.2.1

Dit programma is een herimplementatie van de procedure ontwikkeld in Dialign2. 2, maar met een betere oplossing om te gaan met inconsistente fragmenten, inclusief fragment-chaining. Het implementeert ook een nieuwe aanpak voor het schatten van de waarschijnlijkheid van het willekeurig voorkomen van elk fragment aanwezig in de volgorde die moet worden uitgelijnd. Dialign-T Gebruikt geen vooraf berekende tabellen om gewichtsscores te verkrijgen: Het berekent waarschijnlijkheidstabellen uit verschillende substitutiematrices. Bovendien, de hebzuchtige-achtige multiple alignment algoritme van Dialign2.,2 werd gewijzigd om valse lokale overeenkomsten te voorkomen.

Kalign Versie 1.04

Kalign is een ander programma dat een progressieve uitlijning benadering gebruikt om de best mogelijke MSA te verkrijgen. Het belangrijkste verschil van dit algoritme met andere methoden is dat het gebruik maakt van de Wu-Manber geschatte string matching algoritme bij het berekenen van de afstand tussen sequenties. Het algoritme Wu-Manber meet de afstand tussen twee strings met behulp van een Levenshtein bewerkingsafstand, die een efficiënte zoektocht mogelijk maakt naar mismatches (gedeeld of niet) en patronen die aanwezig zijn in de sequenties., Volgens de kalign ontwikkelaars, deze methodologie maakt een afstand schatting die zo snel als een K-tuple algoritme, maar is nauwkeuriger . De eerste stap in de uitlijningsprocedure is het berekenen van de paarsgewijze afstanden met behulp van de Wu-Manber-benadering. De pairwise afstand schatting wordt gevolgd door een constructie van een gids boom met behulp van UPGMA, die wordt gebruikt in een globale dynamische programmeringsmethode om de sequenties/profielen uit te lijnen., Daarnaast voert het programma een consistentiecontrole uit om de grootste reeks sequentiewedstrijden te definiëren die in de uitlijning kunnen worden ingevoegd, met behulp van een aangepaste versie van de Needleman-Wunsch om het meest consistente pad door de dynamische programmeermatrix te vinden. Kalign werkt ook de posities van pattern matchings bij, die de absolute positie van matches binnen sequenties aanpast aan hun relatieve posities binnen gegenereerde profielen .