Anonim

Temaer

  • Proteinsekvensanalyser
  • programvare

Abstrakt

Den stadig økende størrelsen på sekvensdatabaser forårsaket av utvikling av høy gjennomstrømnings-sekvensering, gir flere justeringsalgoritmer en av de største utfordringene ennå. Som vi viser, er veletablerte teknikker som brukes til å øke justeringskvaliteten, dvs. raffinement og konsistens, ineffektive når store proteinfamilier undersøkes. Vi presenterer QuickProbs 2, en algoritme for flere sekvensjusteringer. Basert på probabilistiske modeller, utstyrt med ny kolonnorientert raffinement og selektiv konsistens, gir den enestående nøyaktighet. Når du analyserer hundrevis av sekvenser, er Quick-Probs 2 merkbart bedre enn ClustalΩ og MAFFT, de tidligere lederne for behandling av mange proteinfamilier. I tilfelle av mindre sett, hvilke konsistrasjonsbaserte metoder som har den beste ytelsen, er QuickProbs 2 også overlegen til konkurrentene. På grunn av lave beregningsbehov for selektiv konsistens og utnyttelse av massivt parallelle arkitekturer, har presentert algoritme lignende kjøretid til ClustalΩ, og er størrelsesordener raskere enn full konsistens tilnærminger, som MSAProbs eller PicXAA. Alle disse gjør QuickProbs 2 til et utmerket verktøy for å tilpasse familier som spenner fra få til hundrevis av proteiner.

Introduksjon

Flere sekvensjustering (MSA) er av avgjørende betydning i biovitenskap. Evnen til å avsløre evolusjonære og strukturelle forhold mellom sekvenser gjør MSA til det grunnleggende verktøyet i en rekke biologiske analyser, inkludert fylogeni, struktur prediksjon, genfinding og mange andre. Hurtig formidling av teknologier med høy gjennomstrømningssekvensering får sekvensdatabaser til å vokse eksponentielt 1 . For å møte dette, er det nødvendig med utvikling av justeringsalgoritmer som er i stand til å behandle tusenvis av sekvenser i rimelig tid.

Blant mange foreslåtte heuristikker for å finne flere sekvensjusteringer, har progressiv skjema blitt den mest populære. Den består av tre trinn: (I) estimering av evolusjonære avstander mellom sekvenser, (II) å bygge et guidetre basert på avstandene, (III) grådig tilpasning av sekvenser i rekkefølgen beskrevet av treet. Den klassiske representanten for progressive aligners med mer enn 50 000 sitater (Google Scholar, oktober 2016) er ClustalW 2 . Den største ulempen ved progressive algoritmer er utbredelsen av feil fra bunnnivået til styretreet til sluttresultatet. Mange teknikker har blitt innført for å motvirke dette problemet. Historisk sett var den første tilnærmingen å fikse feil som ble gjort på det progressive stadiet ved iterativt å raffinere utgangsjusteringen 3 . Denne ideen har blitt vellykket vedtatt av en rekke algoritmer som MAFFT 4, MUSCLE 5 eller MSAProbs 6 . Et annet iterasjonsprogram er innført i ClustalΩ 7, som kombinerer omberegninger av et guide-tre og profil skjulte Markov-modeller på grunnlag av en foreløpig tilpasning. Dette resulterer i en overlegen nøyaktighet for store proteinfamilier. En alternativ måte å legge til rette for progressiv heuristikk er å forhindre feil under justeringskonstruksjon. Dette kan oppnås på ulike måter. En metode er å benytte informasjon fra suboptimale justeringer, for eksempel ved å beregne bakre sannsynligheter på grunnlag av par skjulte Markov-modeller (ProbCons 8 ), partisjonsfunksjon (ProbAlign 9 ), eller begge disse (MSAProbs). En annen tilnærming er å inkorporere kunnskap fra andre parvise justeringer ved behandling av gitt par sekvenser / profiler. Teknikken er kjent som konsistens, og ble opprinnelig brukt i T-Coffee 10 . Konsistens har vist seg å øke tilpasningskvaliteten betydelig og har blitt vellykket vedtatt i forskjellige varianter av en rekke progressive (MAFFT 11, ProbCons, MSAProbs) og ikke-progressive algoritmer (PicXAA 12 ). Imidlertid begrenser en betydelig ulempe av konsistensbaserte metoder, dvs. overdreven beregningskompleksitet med hensyn til antall sekvenser, deres anvendelighet til familier på omtrent hundre medlemmer. Følgelig bruker ikke algoritmer som tillater tusenvis eller flere sekvenser å bli justert som Kalign2 13, Kalign-LCS 14, FAMSA 15, ClustalΩ eller MAFFT i PartTree-modus 16, konsistens.

I denne artikkelen gir vi et nytt innblikk i effekten av forfining og konsistens på den progressive tilpasningen. Vi undersøkte store sekvenssett som viste at nøyaktigheten av de nevnte teknikkene skaleres utilfredsstillende med antall sekvenser. Spesielt, når sett med hundrevis eller tusenvis av sekvenser er av interesse, har eksisterende avgrensningsvarianter liten effekt på justeringskvalitet, mens konsistens reduserer den ved å introdusere mer støy enn relevant informasjon. Vi presenterer nye ideer for å overvinne disse problemene. dvs. kolonneorienterte raffinement og selektiv konsistens.

Forskningen ble basert på QuickProbs-algoritmen 17, som er en etterfølger av MSAProbs-en av de mest nøyaktige multiple sekvensjustere 6 . Takket være bruken av massivt parallelle arkitekturer, er QuickProbs størrelsesorden raskere enn MSAProbs beholder kvaliteten på resultatene. Vi introduserer QuickProbs 2, som er en betydelig forbedring i forhold til forgjengeren. Kolonnorientert raffinement konvergerer til justeringer av høyere kvalitet enn eksisterende metoder, mens selektiv konsistens inkorporerer mest relevant informasjon fra parvise justeringer, effektivt reduserer antall feil i en progressiv skjema, også for store sett med sekvenser. Videre reduseres selektiviteten dramatisk beregnende innsats relatert til konsistens. Dette, sammen med optimalisert implementering, tillater QuickProbs 2 å produsere justeringer som er overlegne forforløperen i en brøkdel av tiden. Som et resultat er presentert algoritme den mest nøyaktige justeren når man undersøker proteinfamilier som spenner fra få til hundrevis av sekvenser. Fasilitetene som nukleotidmodus eller bulkbehandling øker brukbarheten til QuickProbs 2 ytterligere.

metoder

I dette papiret presenterer vi QuickProbs 2, en romanalgoritme for flere sekvensjusteringer. Den består av fire trinn: (I) beregning av bakre sannsynlighetsmatriser, (II) konstruksjon av styretreet, (III) konsistenstransformasjon, (IV) konstruksjon av sluttjusteringen etterfulgt av iterativ forfining. Posterior sannsynlighet matriser beregnes for alle sekvenspar på grunnlag av skjult Markov-modell 18 og partisjonsfunksjon 19 . Matrices brukes videre for å etablere maksimale forventede nøyaktighetsjusteringer. Justeringspoeng blir brukt til å estimere parvise avstander som er gitt som en inngang for den veide UPGMA algoritmen 20 for styretrengekonstruksjon. For å inkorporere informasjon fra alle parvise justeringer når de justerer gitt par av sekvenser / profiler, blir bakre matriser multiplisert med hverandre under konsistentransformasjon. Deretter blir sekvensene gradvis justert i styretrekkefølgen med en bruk av de transformerte bakre matriser. Dette etterfølges av den iterative raffinement.

De viktigste fremskrittene med hensyn til eksisterende metoder ble oppnådd i trinn III og IV. QuickProbs 2 har blitt utstyrt med en ny kolonneorientert raffinement og selektiv konsistens, som beskrives videre i følgende underavsnitt. Et eget underavsnitt handler om andre algoritmiske forbedringer og nye fasiliteter introdusert i den presenterte algoritmen. Til slutt beskriver vi i detalj referanse datasett og tiltak som brukes til kvalitetsvurdering.

Kolonneorienterte raffinement

Forfining ble utformet for å overvinne den viktigste ulempen med progressive algoritmer - feiljusteringer forårsaket av forplantning av feil fra tidlig progressive trinn opp føringstreet. Prosedyren bruker vanligvis en iterativ ordning med alternative splittelser og justeringer og inkorporerer en objektiv funksjon for resultatevaluering. En rekke raffinementstrategier ble undersøkt i litteraturen 21, 22, 23 . Blant dem er tilfeldige og treveiledede tilnærminger blitt de vanligste i MSA-algoritmer.

Første revisjon av QuickProbs, på samme måte som ProbCons eller MSAProbs, benytter den tidligere ideen: Hver raffinement iterasjon deler en tilpasning tilfeldig til to horisontale profiler og tilpasser dem etter fjerning av kolonner som bare inneholder hull. Ingen objektiv funksjon er innlemmet. Den betydelige ulempen ved prosedyren er at jo større antall sekvenser, desto mindre er sjansen for å produsere profiler med kun gapskolonner. Som et resultat blir det ikke fjernet noen kolonner i de fleste tilfeller, og den omregnede profilen vil trolig være den samme som den inntastede. Derfor gir det ikke mange forbedringer i nøyaktighet for flere rekkefølge. En alternativ tilnærming, innarbeidet, for eksempel av MUSCLE eller MAFFT, er treveiledning. Den deler opp justeringen ved å bryte tilfeldig valgt gren i styretreet. Ettersom gap-bare kolonner er mer sannsynlig å oppstå på grunn av å samle fylogenetisk relaterte sekvenser i underprofiler, kan denne tilnærmingen potensielt være mer vellykket når store proteinfamilier undersøkes.

Vi presenterer en ny tilnærming til forfinningen som anser kolonner som inneholder minst ett gap. Algoritmen velger tilfeldig en av disse kolonnene og deler innstillingen i to profiler avhengig av gapet i denne kolonnen. Som et resultat blir det ved hver raffinement-iterasjon minst en profil forkortet å øke betydelig, sjansen for å omorganisere tilpasningen og gi et høyere kvalitetsresultat. Denne typen raffinement vil bli referert til som kolonneorienterte og, som eksperimenter viser, er den overlegen tilfeldige og trestyrte tilnærminger, spesielt for store sekvenssett. Figur 1 viser anvendelsen av kolonneorienterte raffinement på eksempeljustering.

Iterering av kolonneorienterte raffinement: ( a ) En av kandidatkolonnene (i blå) er tilfeldig valgt som en splitter (avgrenset med en oransje boks); ( b ) justeringen er delt inn i to profiler i henhold til tilstedeværelsen av hull i den valgte kolonne; ( c ) kun gapskolonner fjernes som følges av profiljustering.

Full størrelse bilde

En viktig observasjon er at antall hull i en kolonne, ifølge hvilken en justering er delt, påvirker størrelsen på de resulterende profilene. Jo nærmere er g til halvparten av sekvensen sett størrelse N, desto mer balansert er divisjonen. For å undersøke effekten av ubalanse i profiloppdeling på justeringskvalitet ble kolonnene sortert med hensyn til

. Deretter ble en antatt prosentandel fra begynnelsen eller fra slutten vurdert i tilfeldig utvalg (disse tilsvarer forspenningen mot henholdsvis mer eller mindre balansert deler).

Forbedringen blir ofte lettere ved å introdusere en objektiv funksjon. Bruken av uovervåket SP-poengsum under antatt substitusjonsmatrise og gap-straffemodell (ikke å forvirre med overvåket SP-poengsum beregnet på basis av referansejusteringen) er blant de mest populære 5, 11 . Ikke desto mindre konvergerer maksimering av ikke overvåket SP-poengsum nødvendigvis til biologisk meningsfulle innstillinger 22, 24, spesielt for konsistensalgoritmer 22 . I undersøkelsen foreslår vi justeringslengde som skal brukes som et enkelt og effektivt mål for avgrensningsovervåking. Intuitivt akkumuleres feiljusteringer i påfølgende progressive trinn, noe som fører til at blokker av konserverte symboler blir skiftet i forhold til hverandre. Som et resultat kan man forvente at feilaktige tilpasninger skal være lengre enn de som korrekt identifiserer utviklingen av sekvenser. Denne hypotesen støttes av observasjonen at gjennomsnittsjusteringslengden avtar som kvaliteten øker i sammenhengende raffinement iterasjoner. Derfor introduserte vi til raffinementet et akseptorkriterium for ikke-økende justeringslengde som ytterligere forbedret konvergensen.

I undersøkelsen undersøkte vi også entropi-basert akseptregel for ikke-avtagende trident score (se ref. 25 for definisjonen). Metoden anvender tre komponenter for kolonneprøving: aminosyrebeskyttelse, stereokjemiske egenskaper og tilstedeværelse av hull. Begrunnelsen bak var at korrekt korrigerte kolonner som er strukturelt og funksjonelt konserverte, bør preges av lavere entropi.

Et åpent problem er mottakelsen av presenterte raffinementstilnærminger til overjusteringen, dvs. generering av for korte tilpasninger. De fleste av referansedataene, inkludert de som brukes i vår studie, er basert på struktur, ikke fylogeni. Som et resultat foretrekkes tette innretninger, til tross for at de er uriktige fra det evolusjonære synspunkt 26 . Dette problemet er vanlig for flertallet av sekvensjusteringsmetoder og få forsøk har blitt gjort for å motvirke dette problemet med PRANK 26, 27 og MAFFT 28 som eksemplene.

Selektiv konsistens

I motsetning til raffinement, har konsistensen til hensikt å forhindre feiljusteringer i den progressive ordningen i stedet for å eliminere dem etterpå. For å redusere sjansen for feil, bruker konsistensen informasjon fra alle parvise justeringer når man justerer et par to bestemte sekvenser. Selv om denne tilnærmingen har blitt vellykket anvendt i en rekke progressive MSA-algoritmer, begrenser den overdrevne beregningskostnaden sin anvendelighet til sett med hundrevis av sekvenser. Sievers et al . 29 gjorde en uttømmende studie om skalerbarhet av MSA-algoritmer som undersøker effekten av tilsetning av homologe sekvenser til referansesettet på justeringsnøyaktigheten. For alle observerte metoder ble kvaliteten svekket da mer enn 50 sekvenser ble tilsatt. Forfallet var spesielt bratt for flere konsistensbaserte metoder (f.eks. MSAProbs, ProbCons) som tyder på at for større sett av sekvenser overstiger støy relevant informasjon. Dette har imidlertid ikke blitt bekreftet eksplisitt. De siste forsøkene på å anvende konsistens (spesielt MAFFT G-INS-1 algoritme) på større sett med sekvenser krevde dager med beregninger og uoverkommelig mengde RAM 30 . Det er også uklart om lovende kvalitet på resultatene skyldtes å utføre fulle parvise justeringer for styretrebygging eller takket være konsistensen.

I QuickProbs 2, på samme måte som forgjengeren, er konsistensen avhengig av transformerende bakre sannsynlighetsmatriser beregnet på trinn I. La U angi et sett med inngangssekvenser og S xy være en bakre matrise for sekvenser x, yU. I QuickProbs 1 inkorporerer konsistensen S xy informasjon fra alle andre sekvenser i henhold til formelen

med at du er vekten av sekvensen du ble etablert under trekonstruksjon. Inkluderingen av informasjonen fra z, dvs. tilsetningen av w z S xz S zy komponent vil bli referert til som en avspenning av S xy over z . En enkelt konsistent transformasjon er avhengig av å slappe av alle bakre matriser gjennom alle sekvenser. Denne prosessen kan bli iterert, dvs. matrices beregnet som en utgang fra en transformasjon kan brukes som en inngang for en annen.

Tiden kompleksiteten av O ( N 3 L 3 ), med L er sekvenslengden, gjør dette stadiet svært tidkrevende. Nøyaktig, bakre matriser er representert i en sparsom form med en sparsitetskoeffisient β <1. Som angitt i Støttende informasjon til ref. 17, avhenger tidskompleksiteten av strukturen av sparsomme matriser og varierer fra O ( β 2 N 3 L 3 ) til O ( βN 3 L 3 ). Likevel, som QuickProbs kommer med en rask avspenningsalgoritme egnet for grafikkprosessorer, kunne vi undersøke effekten av konsistens på sett som overstiger tusen sekvenser. Som vist i eksperimentell seksjon, reduserte prosedyren tilpasningskvaliteten for proteinfamilier av slike størrelser.

Utfordringen som naturlig oppstår, er å anvende konsistens bare på sekvenser som bærer det meste av informasjonen. Spesielt har vi undersøkt om det er en sammenheng mellom informasjonsinnhold og evolusjonært forhold til sekvenser som er involvert i konsistensen. Til dette formål introduserer vi selektiv konsistens . Gitt x, y, z sekvenser og d xz, d yz avstander, bakre matrise S xy er avslappet over sekvens z hvis en aggregeringsfunksjon α ( d xz, d yz ) oppfyller gitt tilstand. I undersøkelsen undersøkte vi to forskjellige d xy- tiltak:

  1. poengbasert avstand beregnet på stadium I, rangert og normalisert til [0, 1] intervall,

  2. trestyrt avstand definert som et antall noder i et minimalt subtre som inneholder både x og y .

Maksimum, minimum eller sum kan brukes som eksempler på aggregeringsfunksjon α . Selektivitet ble brukt enten ved:

  1. deterministisk terskel a på vilkårlig verdi T,

  2. Påføring av stokastisk filtrering.

Sistnevnte krever definisjon av en filterfunksjon F som kartlegger verdien av aggregeringsfunksjonen a ( d xz, d yz ) til sannsynligheten for å utføre avslapping over sekvens z, dvs.: F ( α ): α ( d xz, d yz ) → [0, 1]. Form av filterfunksjonen bestemmer hvilke sekvenser som er foretrukket i konsistensprosedyren (f.eks. Nært eller fjernt beslektet). Prosedyren for stokastisk selektivitet for matrise S xy over sekvens z virker i henhold til følgende trinn:

  1. beregne verdien av α 0 = α ( d xz, d yz ) i henhold til antatt avstandsmåling d og aggregeringsfunksjon α,

  2. bestem verdien av filterfunksjonen F ( α 0 ),

  3. prøv et tilfeldig tall p fra uniformfordelingen [0, 1],

  4. hvis F ( α 0 ) ≤ p, utfør avspenning av S xy over z .

Da kombinasjon av trebaserte avstander og deterministiske terskler ga overlegne resultater, forklarer vi denne varianten av selektivitet i figur 2.

Triangler representerer subtre med sekvenser x, y, z og u . Ved hver node er det gitt en størrelse på en subtree. I eksemplet aksepterer selektivitetsprosedyr avspenning av S xy gjennom z som α ( d xz, d zy ) ≤ T (grønn oval). Samtidig utelukker du sekvens u fra konsistensen på grunn av α ( d xu, d uy )> T (rød oval).

Full størrelse bilde

Bivirkningen av selektivitet er variabiliteten i antall avslappninger utført for forskjellige bakre matriser. Følgelig, jo større antall sekvenser som gjennomføres konsistenstransformasjon, jo svakere er informasjonen fra den opprinnelige S xy sammenlignet med matrices det multipliseres med. F.eks. Bidrar en matrise avslappet av tretti sekvenser til transformasjonen ti ganger mindre enn den avslappet av tre. For å overvinne dette analyserte vi i tillegg effekten av multiplikasjon av S xy- elementer med en koeffisient h xy . Verdien av h xy er satt individuelt for hver matrise og varierer lineært fra 1, når det ikke utføres noen relaxeringer av S xy, til brukerdefinert verdi h, når maksimalt antall avslappninger under valgte selektivitetsinnstillinger er gjort (200 i vårt tilfelle) . Dette gjør at sett av forskjellige størrelser kan håndteres ordentlig.

Andre algoritmiske forbedringer

Til tross for å fokusere QuickProbs 2 forskning på å forlenge raffinement og konsistensstrinn, var beregning av bakre matriser også gjenstand for noen modifikasjoner. Kvalitet forbedringer inkluderer å erstatte Gonnet160 matrisen for partisjon funksjon beregning av VTML200, som viste seg å være mer nøyaktig 31 . Dette ble etterfulgt av trening av partisjonsfunksjonsparametere, dvs. gapstraff og -temperatur på BAliBASE 3 32- benchmark med bruk av NOMAD-algoritmen 33 for optimalisering av ikke-jevne funksjoner. Andre endringer ble introdusert for å forkorte kjøretiden. De inkluderer omforming av grafikkprosessorberegninger for å håndtere sekvenser av hvilken som helst lengde, optimalisering av både CPU- og GPU-koder, og bruk av mer effektiv minneallokering. Som et resultat er bakre beregningsstadiet i QuickProbs 2 mer nøyaktig enn sin forgjenger, noe som er merkbart raskere. Den typiske oppgraderingen av stadium I på moderat størrelse familier var todelt. Når familier av lange proteiner ble undersøkt som BB20010 fra BAliBASE 32 (29 sekvenser med 1, 045 aminosyrer i gjennomsnitt), var beregningen av bakre matriser 10 ganger raskere enn i QuickProbs 1.

Den presenterte algoritmen er utstyrt med en nukleotidmodus hvor HOXD-substitusjonsmatrise 34 og GTR-evolusjonsmodellen 35 anvendes. Nøyaktig modus, som i QuickProbs 1 justerte en sparsitykoeffisient i bakre matriser, støttes ikke lenger på grunn av overdreven beregningstid og mangel på signifikant innvirkning på resultatene.

På grunn av forskjellig oppførsel av konsistens avhengig av settstørrelse, blir antall transformasjoner justert til antall sekvenser (2 for N <50, 1 ellers). Det ble også oppdaget at for to konsistenttransformasjoner er 30 iterasjoner av raffinement i stedet for standard 200 tilstrekkelig for å oppnå tilfredsstillende konvergens.

Som QuickProbs 2 bruker OpenCL, kan den utføres på forskjellige massivt parallelle enheter som NVidia og AMD GPUer. Videre har presentert programvare også muligheten til å bli kjørt på sentral prosessor uten OpenCL. For enkelhets skyld er QuickProbs 2 utstyrt med en massemodus slik at et hvilket som helst antall sekvenssett kan behandles under en enkelt løp. Nødvendigheten av å lagre bakre matriser for alle par av sekvenser, forårsaker at minnet er den største begrensningsfaktoren for settstørrelsen. Av denne grunn gir QuickProbs 2 muligheten til å passe analyse i en brukerdefinert mengde RAM ved å redusere sparsitetskoeffisienten i bakre matriser. Naturligvis påvirker justeringen kvaliteten og er bare mulig innenfor visse grenser.

Nøyaktighetsvurdering

Nøyaktigheten til algoritmer ble vurdert på flere benchmark datasett som følger med referansejusteringer. Disse var BAliBASE 32, PREFAB 5, SABmark 36, HomFam 37 og BaliFam 29 . De tre tidligere ble lastet ned i et standardisert FASTA-format fra Robert Edgars nettside 38 og består av små og moderate sekvenser (opptil titalls sekvenser i de fleste tilfeller). Sistnevnte ble konstruert ved å berikke henholdsvis Homstrad 39- og BAliBASE-referanser, med full proteinfamilier fra Pfam 40 . Antall sekvenser i BaliFam-settene er i størrelsesorden 1000 mens Homfam inneholder mye større familier med over 100 000 medlemmer. Begge referansene ble etterbehandlet ved å fjerne dupliserte sekvenser som vises numerisk på grunn av generasjonsprotokollen. Dette var motivert av det faktum at duplikater kan påvirke nøyaktigheten av analyserte algoritmer og kan rettes opp etter at justeringen er ferdig.

Etterbehandlet BaliFam inneholdt 218 sett med 934 sekvenser i gjennomsnitt. Som hovedfokus fokuserer forskningen på skalerbarheten av presenterte metoder med hensyn til antall sekvenser, ble BaliFam rekursivt resamplert for å oppnå mindre tallrike sett: første referanse i to sett med 800 sekvenser, hver av disse i to sett med 600, og så videre. Endelig ble elementer på samme nivå av pyramiden samlet sett sett som referert til som BaliFam-800 × 2, BaliFam-600 × 4, BaliFam-400 × 8 og BaliFam-200 × 16. Denne protokollen inneholder mindre sett i større dem og bevarer representativitet for alle problemstørrelser. Når det gjelder HomFam, etter duplikatfjerning, ble alle dets sett tilfeldig nedsamplet til 1300 medlemmer med en garanti for å bevare sekvenser som er tilstede i referanselinjene. Dette var motivert av at originale HomFam-sett var for store til å bli behandlet av QuickProbs 2 på grunn av minnekrav. Samplet referanse vil bli referert til som HomFam 1K og inneholdt 94 familier med 1, 093 sekvenser i gjennomsnitt. Detaljert histogrammer av familiestørrelser i BaliFam og HomFam 1K er presentert i tilleggs figur 1.

Kvalitetsvurdering ble utført med veletablerte beregninger relatert til referansejusteringer. De er overvåket sum av par (SP) og total kolonne (TC) score definert som en brøkdel av henholdsvis korrekt justerte symbolpar og kolonner. Når et enkelt kvalitetsmål var nødvendig, for eksempel for visualisering, et geometrisk middel

av de nevnte resultatene ble ansatt. Separate diagrammer for SP- og TC-tiltak er gitt som supplerende tall.

resultater

Refinement

I de første forsøkene undersøkte vi tilfeldige og treveiledede forbedringer sammen med forskjellige varianter av ny kolonnorienterte prosedyre. Etter hvert som raffinement ble oppnådd av justeringsalgoritmer tidligere til konsistens, ble sistnevnte deaktivert i denne eksperimentelle delen. BaliFam-800 × 2 benchmark ble valgt som en representant for store proteinfamilier i stedet for BaliFam fordi den inneholder to ganger så mange sett som reduserer resultatvariabiliteten. Effekten av påfølgende raffinement iterasjoner er presentert i figur 3a, mens skalerbarhet av raffinement med hensyn til settstørrelsen etter 200 iterasjoner kan observeres i figur 3b.

Sammenligning av raffinementstrategier: ( a ) effekt av sammenhengende iterasjoner på BaliFam-800 × 2, ( b ) skalerbarhet i forhold til antall sekvenser i et sett etter 200 forfinninger.

Full størrelse bilde

Som diagrammer viser, for mange proteinfamilier som de i BaliFam-800 × 2, ga det ikke noen økning i nøyaktigheten i sammenhengende tilfelleforbedringer. Videre var tilfeldig prosedyre kun lønnsom for BAliBASE og fra BaliFam-200 × 16 hadde det ingen effekt på resultatene. Utførelsen av trerådd raffinement var merkbart bedre, men forbedringen gikk ned med det økende antall sekvenser. Den motsatte situasjonen oppstod i tilfelle kolonneorienterte raffinement. Ikke bare var det bedre enn konkurrerende tilnærminger, men forskuddene over ikke-raffinerte produksjonen ble preget av perfekt skalerbarhet. Nemlig økte den fra 2% på BAliBASE til nesten 7% på BaliFam, og bekreftet valget av gap-only kolonner som et valg for store proteinfamilier. Når man analyserer effekten av splittet ubalanse på justeringskvalitet, er det synlig at innsnevring av delmengden av kolonner som vurderes i utvalget til 50% eller 20% av de mest balanserte / ubalanserte posisjoner forårsaket nøyaktighetsforfall. Følgelig ble versjonen uten preferanse valgt for videre utredning.

De endelige raffineringseksperimenter vedrørte effekten av forskjellige akseptregler. De var ikke-økende justeringslengde og ikke-avtagende entropi score. Som vist i figur 3, er den tidligere forbedrede raffineringskonvergensen for større sekvenssett bare litt underordnet uovervåket variant på BAliBASE. I kontrast utførte entropi-scoring utilsiktet på alle analyserte sett. Som et resultat ble kolonneorienterte raffinement med lengdeovervåking valgt for QuickProbs 2. Diagrammer som viser innflytelse av raffinement på SP og TC-tiltak separat, finnes i tilleggs figur 3.

For å undersøke nøyaktigheten av kolonneorienterte raffinement i ulike klasser av justeringsproblemer ble alle BaliFam-undergrupper analysert uavhengig. De korresponderer med BAliBASE 3 referansesett som representerer: likeverdige sekvenser på 0-20% (ref. 11) og 20-40% (ref. 12) identitet, familier med foreldreløse (ref. 2), divergerende underfamilier (ref. 3) store utvidelser (ref. 4), og store innføringer (ref. 5). Figur 4 presenterer kvalitetsresultater sammen med relative justeringslengder for de ikke-overvåkede og overvåkede algoritmer. Den første observasjonen vedrører de relative justeringslengder som avtar med påfølgende raffinement-iterasjoner for begge algoritmevarianter. Reduksjonsraten var større i tilfelle den kontrollerte prosedyren. Ved sammenligning av nøyaktigheter ble det største fremskrittet av den overvåkede varianten observert på refs 2, 12. I tilfelle av refs 3, 4 var fordelen mindre tydelig. På refs 5, 11 ble begge raffinementsvarianter utført på samme måte. En interessant observasjon er at justeringer produsert av den overvåkede varianten var betydelig kortere enn like nøyaktige resultater av den ukontrollerte prosedyren. En av mulige forklaringer er at innføring av akseptkriteriet for ikke-økende lengde fører til at utjevningsjusteringer blir tettere i gapped-regioner som er utenfor referanseevalueringsblokker. For å undersøke rekonstruksjonskvaliteten av disse regionene, bør syntetiske, fylogeni-bevisste familier som de som foreslås av 28, benyttes. Derfor er følsomheten for presentert tilnærming til overjustering et åpent problem.

Justeringskvaliteter og deres relative lengder er representert som henholdsvis kontinuerlige og punkterte linjer.

Full størrelse bilde

Konsistens

Figur 5a viser effekten av de tradisjonelle (ikke-selektive) konsistensherreringene på utvalgte referansemål etter 200 forbedringer. For mindre sett (BAliBASE, PREFAB, SABmark) innførte konsistensen relevant informasjon, forhøyet resultatkvalitet. Likevel intervenerte det samtidig støy som akkumulerte for store sett av sekvenser som forårsaket nøyaktighetsforfall selv etter den første iterasjonen (800 × 2). Figur 5b viser at konsistensen er skadelig for store referanser uavhengig av raffinering iterasjon. Figur 6a viser at støyen begynte å overstige relevant informasjon for N> 400.

( a ) Effekt av konsistensteerasjoner på utvalgte referanser. Analyse av konsistens på BaliFam-800 × 2: ( b ) effekt av stokastisk avstandsrelatert filtrering, ( c ) selektivitetsvarianter for nært beslektede sekvenser, ( d ) vekting av originale bakre matriser med h xy ∈ [1, h ] koeffisient. Justeringskvaliteter fra diagrammer ( a, c ) målt etter 200 forbedringer.

Full størrelse bilde

Scalability of consistency etter 200 refinement iterations: ( a ) justeringskvalitet, ( b ) kjøretid på skrivebordskonfigurasjon med GeForce GPU. Siden hvert referanse på den horisontale akse inneholder to ganger mindre testtilfeller, ble dets forgjenger ganger ganger som om alle settene var like mange.

Full størrelse bilde

Klart å velge kun en del av sekvenser for konsistens kan potensielt øke effektiviteten av prosedyren. For å undersøke en sammenheng mellom informasjonsinnhold og evolusjonært forhold mellom sekvenser som er involvert, brukte vi trekantstokastiske filtre med en forventet akseptasjonsrate på 10%. De var lavpass, mid-pass og high-pass filtre som fremmer konsistens over henholdsvis: tett, mildt og fjernt relaterte sekvenser. Formen på filterfunksjonene er presentert i tilleggs figur 2. Avstander ble beregnet som justeringsscorer fra trinn I, rangert og normalisert til [0, 1], summen ble brukt som en aggregeringsfunksjon a . Figur 5b viser at nært beslektede sekvenser introduserer mer informasjon til konsistensen, og bør derfor foretrekkes ved utvelgelsen. Foruten stokastisk filtrering ble deterministisk selektivitet basert på en struktur av styretreet undersøkt. Konsistensen over sekvensen z ble utført når summen eller maksimumet av trebaserte avstander d xz og d yz var mindre enn antatt terskel T. Sammenligningen av selektivitetsstrategier (figur 5c) demonstrerer den deterministiske varianten med maksimal funksjon tersklet ved

å utføre det beste. Det var bedre enn versjonen uten konsistens uavhengig av raffinement iterasjon med unntak av r = 0 poeng hvor ingen konsistens vant (figur 5d). Effekten av konsistens som bare var lønnsom når den ble parret med forfining, ble ikke observert på mindre sett. For å få dypere innblikk i dette fenomenet, er det nødvendig med mer detaljert undersøkelse av gjensidig avhengighet mellom konsistens og raffinement.

Som et neste trinn analyserte vi effekten av forsterkning av det opprinnelige S xy- signalet ved å multiplisere dets elementer med koeffisient h xy lineært skalert i [1, h ] -intervall. Den største forbedringen i justeringskvaliteten var for h = 3 (se figur 5d) og ble observert for alle sett med 200 eller flere sekvenser (figur 6a). Samtidig forhindret automatisk justering av h xy, avhengig av antall avslappninger, fra nøyaktighetsfall på BAliBASE som inneholder mye mindre sett. Diagrammer som viser innflytelse av konsistens på SP- og TC-tiltakene separat, finnes i tilleggs-figurene 4 og 5.

Det avgjørende ved selektiv konsistens er de lave beregningsbehovene. For N ≥ 200 er det omtrentlig antall avslappninger for hver bakre matrise konstant. Som et resultat er prosessens tidskompleksitet O ( N 2 L 3 ) som er en merkbar forbedring over full konsistensvariant. Sammenligningen av utførelsestider (figur 6b) viser at for store sett av sekvenser var tid overhead relatert til selektiv konsistens ubetydelig sammenlignet med andre QuickProbs 2-trinn.

Sammenligning med andre algoritmer

Sammenligningen av justeringsprogramvare på benchmark datasett er gitt i tabell 1. Algoritmene ble utført på skrivebordskonfigurasjon (detaljer om maskinvarekonfigurasjoner vil bli forklart senere). Programvarepakker egnet for parallellbehandling ble kjørt med 12 behandlingstråder for å fullt ut utnytte multi-core-arkitekturen til CPU.

Full størrelse bord

For små sett med sekvenser (BAliBASE, PREFAB og SABmark), konkurrerer QuickProbs 2 med andre konsistrasjonsbaserte algoritmer. Eksperimenter viser QuickProbs 2 for å overvinne dem med liten margin (avstanden til den nest beste overstiger ikke ett prosentpoeng på både SP og TC) med unntak av SABmark hvor GLProbs 41 tok ledelsen. Dette kan forklares ved at GLProbs er utstyrt med lokale justeringer Markov-modeller, som er spesielt lønnsomme på langt relaterte sekvenser i SABmark. PicXAA, den eneste ikke-progressive algoritmen i sammenligningen, er også dårligere enn QuickProbs 2. For store sett med sekvenser (BaliFam og HomFam 1K ) ble konsistensmetoder ikke anvendelige på grunn av maskinvarebegrensninger. Dessuten var nøyaktigheten av konsistens ofte utilfredsstillende, som i MSAProbs-saken. Av disse grunner ble ClustalΩ valget da mange justeringer var av interesse. Likevel, takket være kolonneorienterte raffinement og selektiv konsistens, var QuickProbs 2 merkbart mer nøyaktig enn ClustalΩ på begge store sett. F.eks. Tilsvarer den største fordelen på BaliFam i TC-score nesten 25% mer vellykkede justerte kolonner. Når man vurderer ClustalΩ med to kombinerte iterasjoner aktivert, var QuickProbs 2 fortsatt overlegen med en rettferdig margin. Figur 7 viser en detaljert sammenligning av de presenterte algoritmen og ClustalΩ-varianter på BaliFam og HomFam 1K- benchmarks. For alle familier i et referansepunkt ble absolutt fordelene ved QuickProbs over konkurrerende programvare i SP- og TC-tiltak bestemt. For hvert mål ble forskjellene sortert og plottet på et diagram som to uavhengige serier. Poengene over den horisontale akse representerer sett på hvilke QuickProbs 2 var overlegen, de nedenfor nedenfor tilsvarer motsatt situasjon. På denne måten kan man vurdere hvilken del av datasettet og i hvilken grad en algoritme utførte seg bedre enn den andre. Fremskrittet til QuickProbs 2 over standardvariant av ClustalΩ er klart: På begge analyserte referanser var vår algoritme overlegen til konkurrenten på omtrent 3/4 familier. Dette var også tilfellet for ClustalΩ-iter2 på HomFam 1K . Litt annerledes situasjon var for BaliFam, hvor det ble muliggjort forbedret ClustalΩ-resultater som muliggjør kombinert iterasjoner. Selv om det fortsatt var klart underordnet QuickProbs 2.

For hvert kvalitetsmål (SP / TC) ble forskjeller på individuelle proteinfamilier sortert og plottet som to uavhengige serier. Poengene over den horisontale akse representerer sett på hvilke QuickProbs 2 var overlegen, de nedenfor nedenfor tilsvarer motsatt situasjon.

Full størrelse bilde

Effekten av presentert algoritme som er verre enn ClustalΩ på flere testfall er naturlig og er også synlig når man sammenligner andre algoritmer. For eksempel ble kombinert iterasjoner rapportert å øke kvaliteten på ClustalΩ 7, 29 resultater betydelig . Men når man analyserer forskjeller på bestemte proteinfamilier, er det sett som standardkonfigurasjonen er mer nøyaktig (figur 8). Dette kan forklares av det høye mangfoldet av justeringsproblemer, som hindrer utviklingen av algoritmer som er overlegen til konkurrentene systematisk på alle testtilfeller. Derfor er den statistiske analysen av resultatene nødvendig for å kunne vurdere ytelsen til undersøkte metoder på riktig måte. Betydningen av rapporterte forskjeller ble verifisert ved bruk av Wilcoxon signert rang test (Tabell 2). For å kontrollere familievise feil ved a = 0, 05 ble Bonferroni-Holm-korreksjonen påført. Lav p-verdi for BaliFam og HomFam 1K gir sterkt bevis på at QuickProbs 2 er den beste algoritmen for justering av store sett med sekvenser, også i forhold til ClustalΩ-iter2 og MAFFT-L-INS-i. Mangelen på betydning ble observert i få tilfeller angående bare små sett (inkludert fordelen med GLProbs over QuickProbs 2).

For hvert kvalitetsmål (SP / TC) ble forskjeller på individuelle proteinfamilier sortert og plottet som to uavhengige serier. Poengene over den horisontale akse representerer sett på hvilke ClustalΩ-iter2 var overlegen, de nedenfor nedenfor tilsvarer motsatt situasjon.

Full størrelse bilde

Full størrelse bord

Overlegen nøyaktighet av QuickProbs 2 på store proteinfamilier faller sammen med rimelige beregningsbehov. QuickProbs 2 kan sammenlignes med standardmodus for ClustalΩ når det gjelder utførelsestider og størrelsesordener raskere enn konsistensbaserte metoder (MSAProbs trengte over en uke for å fullføre BaliFam, QuickProbs 1 klarte ikke å kjøre riktig på grunn av minnekrav). Som QuickProbs 2 bruker OpenCL, kan den utføres på forskjellige massivt parallelle enheter som NVidia og AMD GPUer. Videre har presentert programvare også muligheten til å bli kjørt på sentral prosessor uten OpenCL. Som eksperimenter på forskjellige maskinvareplattformer viser (tabell 3), er CPU-varianten 3-10 ganger langsommere enn GPU-versjonen, men fortsatt raskere enn andre algoritmer basert på konsistens.

Full størrelse bord

Flaskhalsen til QuickProbs 2 er minnekravene, spesielt nødvendigheten til å lagre bakre matriser for alle par sekvenser. F.eks. Var 8 GB RAM nødvendig for å behandle 1000 sekvenser med lengde 100 eller 300 sekvenser med lengde 500. Når 64 GB var tilgjengelig, presenterte algoritmen vellykket justerte familes av 1300 proteiner med 500 aminosyrer.

Diskusjon

Stadig økende tilgjengelighet av genomiske og proteomiske data åpner nye muligheter for biovitenskap. Likevel er det en stor utfordring for algoritmer for sekvensanalyser, inkludert flere sekvensjusteringer. Økende antall sekvenser er en av de viktigste faktorene som bestemmer vanskeligheten av MSA-problemet. I vår forskning har vi bekreftet raffinement og konsistens, to mest populære kvalitetsmålte teknikker som brukes av progressive aligners, å være ineffektive eller til og med skadelige for sett med hundrevis og flere sekvenser. Vi presenterer QuickProbs 2, en multiple alignment algoritme utstyrt med ny kolonne-orienterte raffinement og selektiv konsistens. Det skaleres godt med antall sekvenser som gir betydelig bedre nøyaktighet enn ClustalΩ-den forrige lederen for å analysere store sett av sekvenser. For mindre tallrike sett ( N <100), når metoder basert på full konsistens som MAFFT-L-INS-i, MSAProbs eller PicXAA er anvendbare, er QuickProbs 2 fortsatt overlegen for konkurrentene. Det som er viktig, oppnås enestående nøyaktighet på kort tid takket være utnyttelsen av massivt parallelle arkitekturer.

Ved å utvide bruken av raffinement og konsistens til omtrent tusen sekvenser, viste vi at sett av forskjellige størrelser krever forskjellig behandling. Et åpent problem er imidlertid skalerbarheten av presentert ideer for familier med titalls eller hundrevis tusenvis av sekvenser som er vanlige i Pfam-databasen. Dette skyldes minnekravene til QuickProbs 2, hovedproblemet som skal løses i fremtidige utgivelser. For slike store sett med sekvenser er ClustalΩ eller MAFFT fortsatt valget.

Andre faktorer som bidrar til kompleksiteten til multiplejusteringsproblemet er sekvenslengder, deres evolusjonære forhold, tilstedeværelse av lange terminalfragmenter osv. Vi tror at fremtidig utvikling av MSA-domene er umulig uten bedre forståelse av innflytelsen av alle disse elementene på justeringsalgoritmer. Spesielt, i lys av de siste, men tvilsomme, funn med hensyn til ytelse av kjedede styretrær i tilpasning av store sett av sekvenser 15, 42, 43, 44 . Vår forskning fører også til noen observasjoner som gjenstår å bli forklart, for eksempel at effekten av konsistens er lønnsom for store proteinfamilier bare når de kombineres med forfining. Dypere involvering av det biologiske samfunnet, som per definisjon er den viktigste mottakeren av flere justeringsalgoritmer, vil overveiende legge til rette for fremskritt i dette området av beregningsbiologi.

QuickProbs 2 kjørbare sammen med kildekoden er tilgjengelig på //github.com/refresh-bio/QuickProbs. Alle undersøkte datasett kan lastes ned fra //dx.doi.org/10.7910/DVN/7Z2I4X. Webtjeneste for fjernanalyser er under utvikling.

Tilleggsinformasjon

PDF-filer

  1. 1.

    Tilleggsinformasjon

kommentarer

Ved å sende inn en kommentar, godtar du å overholde våre vilkår og retningslinjer for fellesskapet. Hvis du finner noe fornærmende eller som ikke overholder våre vilkår eller retningslinjer, merk det som upassende.

Anbefalt Redaksjonens