Ongelma rajoitteet
Kuten edellisessä kohdassa, optimaalinen primer-set-pari olisi samanaikaisesti maksimoida tehokkuus ja kattavuus ja minimoida matching-bias. Seuraavassa kuvataan, miten koodasimme määrällisesti nämä rajoitteet.
Tehokkuus
täydellinen primer-set-paria pitäisi tyydyttää useita rajoituksia, joiden tarkoituksena on parantaa PCR-tehokkuus ja spesifisyys ., Samanaikaisesti kaikkien rajoitusten tyydyttäminen on kuitenkin usein epäkäytännöllistä, ja useimmat huipputason alukkeet rikkovat yhtä tai useampaa rajoitusta . Päätimme näin ollen esitellä tehokkuuden optimointi pisteet, koodaus monet rajoitteet, kuten sumea pisteet toimintoja. Tarkemmin sanottuna määrittelimme pisteet summana kymmenen pisteet ehdot: seitsemän sumea pisteet ehdot, jotka liittyvät yhden-pohjamaali tehokkuuden rajoitteet, keskimäärin kaikissa pohjamaalit pohjamaali-set-paria, plus kolme pisteet liittyvät ehdot tehokkuutta primer-set-paria kokonaisuutena., Koska kaikki ehdot on tarkoitus vaihdella välillä 0 ja 1, optimointi pistemäärä vaihtelee 0 (vähäinen tehokkuus) 10 (maksimaalinen tehokkuus).
Yleisesti ottaen, meidän sumea pisteet lasketaan 1 kunkin rajoitus, joka on täysin tyytyväinen, tai, vaihtoehtoisesti, arvo välillä 0 ja 1 riippuen siitä, kuinka lähellä pohjamaali on rajoitus rajoittaa. Esimerkiksi harkitse pohjamaalin sulamislämpötila, Tm. TM: n pitäisi olla täydellisessä pohjamaalissa enintään 52 astetta , mutta 51 on silti siedettävä, joskaan ei ihanteellinen., Tässä tapauksessa sumea pisteytystoimintomme määrittää 1: n 52 asteen tai sitä suuremmille lämpötiloille, 0: n 50 asteen tai sitä alhaisemmille lämpötiloille ja pitää lineaarisesti kasvavaa funktiota 50-52 asteen välillä. Jokainen termi on kuvattu tarkasti, mitä seuraa.
7 single-pohjamaali pisteet ehdot ovat:
-
sulamislämpötila: sulamislämpötila Tm primer on laskettu lähin-naapuri kaava . Pistemäärä on 1, jos Tm ≥ 52, 0 jos Tm ≤ 50 ja (Tm – 50)/2, Jos 50 < Tm < 52.,
-
GC-pitoisuus: GC-pitoisuus on murto-fGC-base paria primer järjestys vastaa joko G (guaniini) tai C (sytosiini). Pistemäärä on 1, Jos 0, 5 ≤ FGC ≤ 0, 7, 0 jos fGC > 0, 7 tai fGC < 0, 4 ja (0, 5 – fGC)/0, 1 Jos 0, 4 ≤ fGC < 0, 5.
-
3′-end stability – score term 1: 3′-end stability-score-termille on määritelty kaksi pistemäärää. Ensimmäinen termi on 0, jos primerin kolme viimeistä emästä koostuvat kokonaan As: sta (adeniineista) ja Ts: stä (tymiineistä) ja 1 muusta.,
-
3′-loppuun vakaus – pisteet aikavälillä 2: toinen pisteet termi on 0, jos viimeisen 5 emäkset sisältävät enemmän kuin 3 Cs tai Gs, ja 1 muuten.
-
Homopolymeerit: homopolymeeri on identtisten nukleotidien sarja. Pistemäärä on 1, jos homopolymeerejä ei ole yli 4 nt, 0,5 jos homopolymeerejä ei ole yli 5 nt, ja 0, jos jonossa on vähintään 5 nt pidempi homopolymeeri.
-
Self-dimeerit: läsnäolo self-täydentävät alueiden välillä parit samanlaisia alukkeet voivat johtaa sukupolven self-dimeerit., Ottaen huomioon, että enimmäismäärä vastaa vuonna aukko vapaa-linjaus välillä pohjamaali ja sen käänteinen täydentää, maxM, pisteet termi on 1, jos maxM ≤ 8, 0, jos maxM ≥ 11 (11 – maxM)/3, jos 8 < maxM < 11.
-
Pinnit: hiusneula voidaan muodostaa läsnäolo self-täydentävyys sisällä primer järjestys, erityisesti sen 3′-päähän., Pisteet termi on 0, jos ainakin yksi aukko-free linjaus välillä pohjamaali ja käänteinen täydentää sen 3′-päähän, sekä viime nukleotidin ja 3 tai enemmän 4 edellisen nukleotidien ottelu, ja 1 muuten.
3 pohjamaali-set-paria pisteet termit määritellään seuraavasti:
-
Sulamis-lämpötila-alue: sulamis-lämpötila-alue ΔTm primer-set-pari on tietokonetomografia kuin maksimi miinus minimi-ja sulamislämpötilat kaikki pohjamaalit asetettu pari., Pisteet termi on 1, jos ΔTm ≤ 3, 0, jos ΔTm ≥ 5 ja (5 – ΔTm)/2, jos 3 < ΔTm < 5.
-
Dimeerit: pidämme enimmäismäärä vastaa maxM kaikissa mahdollisia rinnastuksia välillä kaikki mahdolliset yhdistelmät forward-ja reverse-alukkeiden alkaen pohjamaali-set-pari. Pistemäärä on 1 jos maxM ≤ 8, 0 jos maxM ≥ 11 ja (11 – maxM)/3 Jos 8 < maxM < 11.,
-
Ampliconin pituusalue: koska PCR: n hyötysuhde on tunnetusti pienentynyt ampliconin pituuden kasvaessa , haluamme syntyneiden ampliconien pituuksien olevan kapealla alueella. Haluamme erityisesti välttää amplicons paljon lyhyempi kuin tavoite pituus, koska ne olisi ylivahvistettu suhteessa muihin. Kuitenkin, haluamme pystyä sietää pieni murto-osa harha, jotta vältetään rangaista mahdollisesti arvokasta primer-set-paria, koska vain harvoja sarjoja., Koska edustava joukko bakteeri 16S sekvenssejä, kutsutaan ”referenssijoukko” tästä lähtien, pidämme eroa Δamplen välillä mediaani ja ensimmäinen persentiili ampliconin pituudet kaikissa mahdollisissa amplicons, muodostettu sovittamalla kaikki yhdistelmät eteen-ja taaksepäin alkulukuja set pari vertailujoukko. Pistemäärä on 1, Jos Δamplen ≤ 50 nukleotidia, 0 jos Δamplen ≥ 100 ja (100 – Δamplen)/50, Jos 50 < Δamplen < 100.,
valinta pisteytyksen kriteerit ja oletuksena kynnys perustuu aikaisempaan kirjallisuuteen . Käyttäjä voi kuitenkin asettaa sekä kynnykset että sumeat toleranssivälit eri tavalla kuin oletusarvo ja hänen kokeellisten tarpeidensa mukaan määrittämällä halutut arvot syöttöparametreiksi komentorivityökalua soitettaessa.
Kattavuus
kattavuus pisteet on määritelty useita 16S-sekvenssien hyväksytty vähintään yksi pohjamaali., Kun otetaan huomioon sekvenssit primer ja bakteeri 16S, me määrittelemme siemen viimeisen 5 nukleotidien 3 ’ – lopussa primer ja pidämme 16S sekvenssi vastaa primer jos alue 16S sekvenssi on olemassa, joka vastaa I) siemen primer täsmälleen; ja ii) loput pohjamaali enintään 2 epäsuhtaa . Viitesarjan 16S-sekvenssiä pidetään primer-set-pairin peittämänä, jos vähintään yksi eteenpäin ja yksi käänteinen primer-set-pairissa täsmää sekvenssin kanssa., Koska PCR-hyötysuhde pienenee ampliconin pituudella, asetamme lisärajoituksen: kun otetaan huomioon primer-set-pari ja viitejoukko 16S-sekvenssejä, arvioimme tavoiteampliconin pituuden kaikkien ampliconien pituuksien mediaaniksi, joka saadaan sovittamalla yhteen kaikki etu-ja käänteispalkimoiden yhdistelmät primer-set-parista vertailujoukon kanssa. Tämän jälkeen katsomme, että se ei kata kaikkia 16S-viitesarjoja, joiden ampliconin pituus poikkeaa yli 100 nukleotidia (joko pidempi tai lyhyempi) tavoitepituudesta.,
Matching-bias
Koska viittaus joukko 16S-sekvenssejä ja pohjamaali-set-pari, kolmas optimointi pisteet toimenpiteitä vaihtelun määrä yhdistelmiä forward-ja reverse-alukkeiden matching jokainen 16S viittaus järjestyksessä. Kattavuus vaihtelu johtuu matching bias tulisi minimoida, tai ainakin oli, kun tutkimuksessa on tarkoitus mitata suhteellinen runsaus eri bakteerilajien, koska vahvistus puolueellisuudesta kohti lajin piiriin enemmän yhdistelmiä forward-ja reverse-alukkeita., Mittana matching-bias, me hyödyntää variaatiokerroin kattavuus ympäri kohde sekvenssit, lasketaan kuten keskihajonta yli keskiarvon yhdistelmien määrä, joka vastaa kunkin järjestyksessä.
Viitejoukko 16s sekvenssejä, valmistelu ja selitykset
optimoida kolme pistettä edellä, luotamme edustava joukko bakteeri 16s sekvenssit uutetaan Julkinen 16S sekvenssi tietokanta, GreenGenes ., Se GreenGenes 16S-sekvenssin tietokantaan on järjestetty Toiminnallisia Taksonomisia Yksiköitä (OTUs), jotka ovat sisäkkäisiä klustereita sekvenssit tietokantaan, järjestetty eri tasoilla inter-klusterin samankaltaisuus. Jokaiselle yhtäläisyystasolle jokaiseen klusteriin liitetään referenssijakso, joka on maksimaalisesti samanlainen kuin kaikki muut saman klusterin sekvenssit . Asetettu viite sekvenssit voidaan siten pitää edustavana osajoukko koko sekvenssin tietokantaan, yhä enemmän ja enemmän tarkkoja lisääntyvää inter-klusterin samankaltaisuus (ja, näin ollen, määrä viite sekvenssit)., Valitsimme 85%: n klusterien välisen samankaltaisuuden tasoksi hyvän vaihtokurssin edustavuuden ja monimutkaisuuden välillä, mikä vastaa 5088 edustavaa sekvenssiä, joita käytetään optimointikriteerien arviointiin.
Vaikkakin erittäin herkkä kommentointiin Bakteerit ja Arkkieliöt verkkotunnukset, GreenGenes taksonomian tarkoituksena ei ole erottaa sekvenssejä, jotka kuuluvat eukaryooteissa tai viruksia., Tästä syystä päätimme uudelleen merkitä bakteerien 16S-sekvenssien hyödyntämällä alkuperäisen NCBI taksonomian täsmällisesti, yksi edustaja sekvenssit, vain ne, jotka kuuluvat Bakteerit domain. Koska verkkotunnuksen tiedot puuttuvat NCBI-merkinnästä noin 20% sekvensseistä, suunnittelimme ad hoc-menettelyn bakteerien sekvenssien tunnistamiseksi näistä. Menettely on kuvattu yksityiskohtaisesti Lisäaineistossa (KS.lisätiedosto 1)., Päätimme konservatiivisesti tarkastella vain sekvenssejä, jotka on merkitty bakteereiksi sekä kuratoiduissa, NCBI-pohjaisissa huomautuksissamme että alkuperäisissä GreenGenes-merkinnöissä. Tuloksena oli 4573 edustavaa 16S-sekvenssiä, jotka kuuluivat bakteerien domeeniin.,
Optimointialgoritmi
koska optimaalisten pohjustusvalintojen ongelma edellyttää eri kilpailevien pistemäärien samanaikaista optimointia, se voidaan valaa monitavoitteiseksi optimointiongelmaksi, jossa hakutila on kaikkien mahdollisten pohjustusetuparien joukko ja pisteytystoiminto eli optimointiperuste voidaan määritellä tehokkuuden ja kattavuuden maksimoimiseksi ja yhteensopivuuden minimoimiseksi-bias., Kun useampi kuin yksi kriteeri on optimoitava samanaikaisesti, mutta tavoitteet voidaan optimoida ovat ristiriitaisia, yksi ei yleensä ole kiinnostunut yhtä ratkaisua, vaan joukko Pareto-optimaalisia ratkaisuja, eli joukko ratkaisuja, joista yksikään tavoitteet voidaan parantaa tinkimättä ainakin yksi muu tavoite ., Tuloksena multi-objective optimointi ei ole enää ainutlaatuinen optimaalinen primer-set-pari, kuten yhden tavoitteen optimointi, vaan kokoelma primer-set-paria, jotka eivät ole huonompi kuin muut primer-set-pari ja tiukasti paremmin mukaan ainakin yksi kriteereistä. Tarkemmin sanottuna tri-tavoite optimointi ongelma on maksimoida tehokkuus (E) ja kattavuus (C) optimoinnin tulokset ja minimoida matching-bias (M) pisteet, kuten määritelty edellisessä luvussa, ehdokas primer-set-pareja arvioidaan objektiivista funktion vektorina f = (f, E, f C ; fM)., Kun otetaan huomioon kaksi primer-set-paria p ja p’, sanomme, että p hallitsee p’ (p ≺ p’) Jos ja vain jos f (p) ≠ f (p’), fE (p) ≥ fE (p’), fC (p) ≥ fC (p’) ja fM (p) ≤ fM (p’). Jos p’: tä ei ole olemassa siten, että p’ ≺ p, primer-set-pair p: tä kutsutaan Pareto-optimaaliseksi. Tässä yhteydessä tavoitteena optimaalinen alukkeiden valinta on määrittää (tai arvioitu) määritä kaikki Pareto-optimaalinen primer-set-paria, jonka kuva tri-tavoite tilaa kutsutaan Pareto edessä .
etsiäksemme optimaalista Pareto-rintamaa luotamme Dubois-Lacoste et al: n ehdottamaan kaksivaiheiseen iteroituun best improvement local search approach-lähestymistapaan., ja tehokkaasti hyödynnetään Sambo et al. ja Borrotti ym. optimaaliseen monitavoitteiseen kokeilujen suunnitteluun.
Paikallinen haku alkaa alustavan ratkaisu ja iteratiivisesti jalostaa sitä soveltamalla pieniä paikallisia muutoksia ja arvioidaan aina, kun niiden vaikutus liuoksen laatu; se pysähtyy, kun ei ole enää paikallisia muutoksia voi parantaa ratkaisu. Prosessi iteroidaan useista eri lähtökohdista ja paras koskaan löydetty ratkaisu palautetaan, likiarvona tuntemattomasta optimista ., Yhteinen laajentaminen paikallinen haku multi-tavoite tapauksessa on aloittaa joukko alkuperäisen Pareto-ratkaisuja, näyte yksi ratkaisu edestä, optimoida paikallisten haku satunnainen scalarization ongelma, eli lineaarinen yhdistelmä optimointi tulokset painot näytteitä tasaisesti sattumanvaraisesti yksikön simplex, päivittää Pareto edessä ja kerrata siihen asti, kunnes irtisanominen ehto täyttyy .,
– menettely MULTI-TAVOITE-HAKU, jonka pseudo-koodi on raportoitu, mitä seuraa, saa syöttää haluttu alue amplicon pituudet (rangeamplen), edustava joukko 16S-sekvenssejä (repset), alustavat (mahdollisesti kärjistyä) pohjamaali paria (init) ja määrä käynnistyy (nres). Menettely alkaa valitsemalla init kaikki mahdolliset primer paria halutun amplicon pituus, primer pituus (välillä 17 ja 21 nukleotidien) ja kohde verkkotunnuksen (bakteerit tai Universal).,
degeneroituneet primer-parit muunnetaan ei-degeneroitumattomiksi primer-set-pareiksi ja lisätään arkistoon. Tämän jälkeen menettely iteroi nrest kertaa, joka kerta näytteenotto satunnainen primer-set-pari pstart alkaen Pareto edessä ja satunnainen vektori α suhteellisten painojen optimointi pisteet, jossa painot näyte tasaisesti yksiköstä simplex; menettely, sitten, ratkaisee skalarisaatio multi-objective ongelma, eli yhden tavoitteen ongelma, jossa lineaarinen yhdistelmä kolme tavoitetta suhteellisilla painoilla α on maksimoitu, ja lisää tuloksen arkisto., Tätä tarkoitusta varten tehokkuus, kattavuus ja matching-bias-pisteet normalisoidaan maksimiinsa niin, että jokainen normalisoitu pistemäärä vaihtelee välillä 0 ja 1, ja matching – bias määritellään uudelleen 1-matching-bias, jotta se voidaan maksimoida kuin muut pisteet., ampliconin pituus rangeamplenissa
2 Add to archive the respecting non-degenerate primer-set-pairit
3 for r = 1 to nrest
4 pf = PARETO-FRONT(archive)
5 Sample pstart from pf
6 Sample α from 3, with Σi ai = 1
7 p = LOCAL-SEARCH(pstart , α , repset)
8 add P to archive
9 Return Archive
single-objective optimization saadaan käyttämällä parasta parannusta paikallista hakualgoritmia : aloituspalkista primer-set-pair, local-search algorithm cycles through the primers of the Set-pair and, for each primer, scanning its neighborhood, I.,e. joukko kaikki mahdolliset paikalliset perturbations pohjamaali. Paikallisiin häiriöihin kuuluvat kaikki mahdolliset yhden nukleotidin voltit (arvioimalla kolme muuta mahdollista emästä) sekä kaikki yhden nukleotidin mahdolliset lisäykset ja poistumat ääreisosissa., Etsi ratkaisu tilaa on tehdä paras parannus paikallinen haku lähestymistapa: muodostamisen jälkeen koko naapuruston, kuten edellä on selitetty, algoritmi valitsee parhaan naapurin häiritsemisestä, alkaa se tuottaa seuraavan naapurustossa, ja iteroi, kunnes se saavuttaa ratkaisu, joka ei ole parempi naapurin häiritsemisestä löytyy. Menettely päättyy, kun mitään paikallisia parannuksia ei voida soveltaa mihinkään primer-set-pairiin., Painotetun pistemäärän funktio laskee kolme optimointipistettä primer-set-parista ja edustavasta joukosta, moninkertaistaa pisteet suhteellisilla painoilla α ja palauttaa tulosten summan.
– Olemme kehittäneet ohjelmiston työkalu täytäntöönpanoa meidän lähestymistapa ja se julkaistiin GNU General Public Licence kuin mopo16S työkalu (Multi-Tavoite Pohjamaali Optimointi 16S kokeet) klo http://sysbiobig.dei.unipd.it/?q=Software#mopo16S., mopo16S on toteutettu multithreading C++ command line tool; ohjelmisto työkalu perustuu tehokkaita algoritmeja ja tietorakenteita päässä SeqAn library ja käyttää openMP kirjasto multithreading.,>
4 for i = 1 to |pcurr|
5 pri = i: nnen pohjamaali pcurr
6 pnew = pcurr kaikki mahdolliset lisäykset ja poistot, pohja raajoista ja vaihdot pohja pri
7 scorenew = PAINOTETTU-PISTEET(pnew , α , repset)
8 jos scorenew > scorebest
9 pbest = pnew
10 scorebest = scorenew
11 pcurr = pbest
12 palaa pcurr
State-of-the-art primer paria kuin alkuperäinen ratkaisuja
Valitsimme online-tietokanta probeBase lähteenä ehdokas primer-set-paria voidaan käyttää alkuperäisen ratkaisuja mopo16S., Tietokanta sisältää yli 500 paria (mahdollisesti kärjistyä) alukkeet ja raportoi kunkin pohjamaali sen järjestyksessä, strand ja asentoon, jossa se vastaa viite 16 Escherichia coli-bakteerin geeni, ja target verkkotunnuksen, jota varten se on suunniteltu (joko Bakteerien, Arkkien tai Universal).,
Annetaan haluttu alue, kohde amplicon pituus panos mopo16S, valitsimme kaikki pohjamaali paria alkaen probeBase tietokanta, joka täyttää kaikki seuraavat ominaisuudet:
-
Amplicon ilman lämpötila halutulla alueella;
-
Pituus sekä pohjamaalit yhtä suuri tai suurempi kuin 17 nt ja pienempi tai yhtä suuri kuin 21 nt;
-
Bakteerit tai Universaali kohde-verkkotunnuksen sekä alukkeita.,
Koska lähestymistapamme on työskennellä sarjaa ei-degeneroitunut pohjamaalit, jos degeneracies joko forward tai reverse primer, me korvata rappeutuneen pohjamaali jossa vastaava joukko ei-degeneroitunut alukkeita, jotka on saatu antamalla kaikki mahdolliset yhdistelmät arvot rappeutua nukleotidien pohjamaali. Esimerkki tästä menettelystä esitetään taulukossa 1.
– Meillä on laskettu kolme tulokset kunkin primer-set-paria ja tunnistettu, näiden joukossa, pohjamaali-set-paria, jotka muodostavat alkuperäisen Pareto edessä.