Problem begrænsninger
Som anført i det foregående afsnit, er et optimalt primer-sæt-pair skal samtidig, maksimere effektiviteten og dækning, og minimere matching-bias. I det følgende beskriver vi, hvordan vi kvantitativt kodede disse begrænsninger.
effektivitet
de perfekte primersætpar skal opfylde flere begrænsninger med det formål at forbedre PCR-effektivitet og specificitet ., Imidlertid, samtidig opfylder alle begrænsninger er ofte upraktisk og de fleste state-of-the-art primere overtræder en eller flere begrænsninger . Vi besluttede således at indføre effektivitet som en optimering score, kodning mange af de begrænsninger som Fu..y score funktioner. Mere præcist, vi definerede vores effektivitet score som summen af ti score vilkår: syv fuzzy score vilkår i relation til enkelt-primer effektivitet begrænsninger, gennemsnit på tværs af alle primere i primer-sæt-par, plus tre score vilkår i relation til effektiviteten af primer-sæt-par som helhed., Da alle udtryk er beregnet til at variere mellem 0 og 1, varierer optimeringsresultatet fra 0 (minimal effektivitet) til 10 (maksimal effektivitet).
Generelt, vores fuzzy score tæller 1 for hver begrænsning, der er helt tilfredse, eller, alternativt, en værdi mellem 0 og 1 afhængig af, hvor tæt primer er, at den begrænsning grænse. Overvej som et eksempel primerens smeltetemperatur, TM. TM skal være større end eller lig med 52 grader i en perfekt primer, men 51 er stadig tolerabel, omend ikke ideel., I dette tilfælde, vores fuzzy scoring funktion tildeler 1 til temperaturer på 52 grader eller større, 0 for temperaturer på over 50 grader eller mindre, og mener, at en lineært stigende funktion mellem 50 og 52 grader. Hvert udtryk er præcist beskrevet i det følgende.
de 7 single-primer score termer er:
-
smeltetemperatur: smeltetemperaturen Tm af en primer beregnes med den nærmeste nabo formel . Score sigt er 1, hvis Tm ≥ 52, 0 hvis Tm ≤ 50 og (Tm – 50)/2 hvis 50 < Tm < 52.,GC-indhold: GC-indhold er fraktionen fGC af basepar i primersekvensen lig med enten G (guanin) eller C (cytosin). Score sigt er 1, hvis 0.5 ≤ fGC ≤ 0.7, 0 hvis fGC > 0,7 eller fGC < 0,4 og (0.5 – fGC)/0.1, hvis 0.4 ≤ fGC < 0.5.
-
3′-end stability – score term 1: to score termer er defineret vedrørende 3′-end stabilitet. Det første udtryk er 0, hvis de sidste tre baser af primeren udelukkende består af As (adeniner) og Ts, (thyminer) og 1 ellers.,
-
3′-enden stabilitet – score sigt 2: den anden score sigt er 0, hvis de sidste 5 baser indeholder mere end 3 Cs eller Gs, og 1 i andet.en homopolymer er en sekvens af identiske nukleotider. Scoreperioden er 1, hvis der ikke er homopolymerer længere end 4 nt, 0,5, hvis der ikke er homopolymerer længere end 5 nt, og 0, hvis der i det mindste er en homopolymer længere end 5 nt i sekvensen.
-
Selvdæmpere: tilstedeværelsen af selvkomplementære regioner mellem par af identiske primere kan føre til dannelse af selvdæmpere., I betragtning af det maksimale antal kampe i en gap-gratis tilpasning mellem en primer med sin reverse-komplementet, maxM score på sigt er 1, hvis maxM ≤ 8, 0 hvis maxM ≥ 11 (11 – maxM)/3, hvis 8 < maxM < 11.
-
hårnåle: en hårnål kan dannes i nærvær af selv-komplementaritet inden for primersekvensen, især ved dens 3′-ende., Scoren sigt er 0 hvis, for mindst gapn gap-fri justering mellem primeren og den omvendte komplement af dens 3′-ende, både den sidste nukleotid og 3 eller flere af de 4 foregående nukleotider match, og 1 ellers.
scoringsbetingelserne for 3 primersæt-par er defineret som følger:
-
Smeltetemperaturområde: smeltetemperaturområdettm for et primer-sæt-par beregnes som Maksimum minus minimum af smeltetemperaturen for alle primere i det indstillede par., Scoringsperioden er 1, Hvis iftm 3 3, 0, hvis .tm 5 5 og (5 – .tm)/2, Hvis 3 < .tm < 5.
-
Dimers: vi overvejer det maksimale antal kampe ma .m på tværs af alle mulige justeringer mellem alle mulige kombinationer af frem og tilbage primere fra et primer-set-par. Score sigt er 1, hvis maxM ≤ 8, 0 hvis maxM ≥ 11 (11 – maxM)/3, hvis 8 < maxM < 11.,
-
Ampliconlængdeområde: på grund af den kendte reduktion af PCR-effektivitet med stigende ampliconlængde ønsker vi , at længderne af de genererede ampliconer skal ligge i et smalt område. Vi ønsker især at undgå ampliconer meget kortere end mållængden, da de ville blive overforstærket i forhold til de andre. Vi vil dog være i stand til at tolerere en lille brøkdel af outliers for at undgå at straffe potentielt værdifulde primer-sæt-Par På grund af nogle få sjældne sekvenser., Givet en repræsentant indstillet af bakteriel 16S sekvenser, kaldet “reference” fra nu af vil vi overveje den forskel Δamplen mellem medianen og den første percentil af amplikon længder på tværs af alle mulige-amplifikation, der er dannet ved at matche alle kombinationer af forward og reverse primere fra det sæt parret med reference sæt. Score udtrykket er 1 hvis ifamplen 50 50 nukleotider, 0 hvis ifamplen 100 100 og (100 -ampamplen)/50 if 50 < .amplen < 100.,
valget af scoringskriterier og standardtærsklen er baseret på tidligere litteratur . Men både grænseværdier og fuzzy tolerance intervaller kan indstilles af brugeren forskelligt fra standard, og i henhold til hans/hendes eksperimentelle behov, ved at angive de ønskede værdier som input-parametre, når du ringer kommando-linje værktøj.
dækning
dækningsresultatet defineres som antallet af 16S-sekvenser, der matches med mindst en primer., I betragtning af sekvenserne af en primer og en bakteriel 16 ‘er definerer vi frø de sidste 5 nukleotider ved 3’ – enden af en primer, og vi betragter en 16S sekvens som matchet af primeren, hvis der findes en region af 16 ‘ erne sekvens, der matcher i) frøet af primeren nøjagtigt; og ii) resten af primeren med højst 2 uoverensstemmelser . En 16S-sekvens fra et referencesæt betragtes som dækket af et primer-set-par, hvis mindst en fremadrettet og en omvendt primer i primer-set-parret matcher sekvensen., Da PCR effektivitet falder med amplikon længde, vi lægger et yderligere pres: givet en primer-sæt-par og en henvisning sæt af 16S sekvenser, vurderer vi target amplicon længde som medianen af længder af alle amplikoner opnået ved at matche alle kombinationer af forward og reverse primere fra primer-sæt-par med reference sæt. Vi betragter derefter som ikke dækket alle 16S reference sekvenser hvis amplicon længde adskiller mere end 100 nukleotider (enten længere eller kortere) fra målet længde.,
Matching-bias
givet et referencesæt med 16S-sekvenser og et primer-set-par, måler den tredje optimeringsresultat variabiliteten af antallet af kombinationer af frem-og tilbage-primere, der matcher hver 16S-referencesekvens. Dækning variation på grund af matchende bias bør minimeres, eller i det mindste tegnede sig for, når undersøgelsen er beregnet til at kvantificere de relative mængder af de forskellige bakterie-arter, på grund af forstærkning bias i retning af de arter, der er omfattet af flere kombinationer af forward og reverse primere., Som et mål for matching-bias udnytter vi variationskoefficienten for dækningen på tværs af målsekvenserne, beregnet som standardafvigelsen over gennemsnittet af antallet af kombinationer, der matcher hver sekvens.
Referencesæt med 16S-sekvenser, forberedelse og annotation
for at optimere de tre scoringer ovenfor er vi afhængige af et repræsentativt sæt bakterielle 16S-sekvenser ekstraheret fra en offentlig 16S-sekvensdatabase, GreenGenes ., Greengens 16S-sekvensdatabasen er organiseret i operationelle taksonomiske enheder (OTUs), som er indlejrede klynger af sekvenser i databasen, organiseret på forskellige niveauer af Inter-cluster lighed. For hvert niveau af lighed er en referencesekvens forbundet med hver klynge, der maksimalt ligner alle andre sekvenser i den samme klynge . Sættet af referencesekvenser kan således betragtes som en repræsentativ delmængde af hele sekvensdatabasen, bliver mere og mere præcis for stigende niveauer af Inter-cluster lighed (og dermed antallet af referencesekvenser)., Vi valgte et 85% inter-cluster lighedsniveau som en god afvejning mellem repræsentativitet og kompleksitet, svarende til et sæt af 5088 repræsentative sekvenser, der skal bruges til at vurdere optimeringskriterierne.
selvom det er meget følsomt ved annotation af bakterier og Archaea-domæner, er Greengens taksonomi ikke designet til at skelne sekvenser, der hører til eukaryoter eller vira., Af denne grund besluttede vi at gentage 16S bakteriesekvenser, der udnytter den originale NCBI-taksonomi for nøjagtigt at identificere blandt de repræsentative sekvenser kun dem, der tilhører Bakteriedomænet. Da domæneinformation mangler i NCBI-annotationen for omkring 20% af sekvenserne, designede vi en ad hoc-procedure til at identificere bakteriesekvenser blandt disse. Fremgangsmåden er beskrevet i detaljer i de supplerende materialer (se yderligere fil 1)., Vi valgte konservativt kun at betragte de sekvenser, der er kommenteret som bakterier, både i vores kuraterede, NCBI-baserede annotation og i den originale Greengens-annotation. Dette resulterede i et sæt af 4573 repræsentative 16S sekvenser, der tilhører bakterier domæne.,
Optimering algoritme
Da problemet med optimal primere valg kræver samtidig optimering af forskellige konkurrerende scores, det kan være støbt som en multi-objektiv optimering problem, hvor søgningen rum er sættet af alle mulige primer-sæt-par og en score-funktion, eller optimering kriterium, kan defineres således, at maksimere effektiviteten og dækning, og minimere matching-bias., Når mere end ét kriterium skal optimeres samtidigt, men de mål, der skal optimeres er modstridende, man normalt ikke er interesseret i en enkelt løsning, men snarere i de Pareto-optimale løsninger, eksempelvis i sæt af løsninger, som ingen af de mål, der kan forbedres, uden at det går mindst et andet mål ., Resultatet af multi-objektiv optimering er ikke længere en unik optimalt primer-sæt-par, som i enkelt-objektiv optimering, men snarere en samling af primer-sæt-par, der ikke er værre end nogen anden primer-sæt-par og strengt bedre i henhold til mindst ét af kriterierne. Mere præcist, for tri-mål, optimering problem for at maksimere effektivitet (E) og dækning (C) optimering scores og minimere matching-bias (M) score, som defineret i det foregående afsnit, kandidat-primer-sæt-par er evalueret i henhold til en objektiv funktion, vektoren f = (f, E ; f ; fM)., Givet to primer-sæt-par s og s’, siger vi, at p dominerer p’ (p ≺ p’), hvis og kun hvis f (p) ≠ f (p’), fE (p) ≥ fE (p’), fC (p) ≥ fC (p’) og fM (p) ≤ fM (p’). Hvis der ikke findes nogen p ‘sådan, at p’ p p, kaldes primer-set-pair p Pareto-optimal. I denne sammenhæng er målet med det optimale valg af primere at bestemme (eller tilnærme) sættet af alle Pareto-optimale primer-sæt-par, hvis billede i det tri-objektive rum kaldes Pareto-fronten .
for at søge efter den optimale Pareto-front er vi afhængige af den tofasede itererede bedste forbedring lokal søgning tilgang foreslået af Dubois-Lacoste et al., og effektivt udnyttet i Sambo et al. og låner et al. for den optimale multi-objektiv design af eksperimenter.
lokal søgning Starter fra en indledende løsning og forfiner den iterativt ved at anvende små lokale ændringer og vurdere hver gang deres virkning på opløsningskvalitet; det stopper, når ingen yderligere lokale ændringer kan forbedre løsningen. Processen gentages fra flere forskellige udgangspunkter, og den bedste løsning, der nogensinde er fundet, returneres som en tilnærmelse af det ukendte optimum ., En fælles udvidelse af lokal søgning til multi-mål tilfælde er at starte fra et sæt af de indledende Pareto-løsninger, prøve en løsning fra front -, optimere med en tilfældig scalarization af problemet, nemlig en lineær kombination af optimering scorer med vægte stikprøven ensartet tilfældigt fra den enhed, simplex, opdatere Pareto fronten og gentage, indtil en opsigelse betingelse er opfyldt .,
proceduren MULTI-OBJECTIVE-SEARCH, hvis pseudokode er rapporteret i det følgende, modtager som input det ønskede interval af ampliconlængder (rangeamplen), et repræsentativt sæt 16S-sekvenser (repset), et indledende sæt af (muligvis degenererede) primerpar (init) og antallet af genstarter (nres). Proceduren begynder med at vælge fra init alle mulige primerpar med den ønskede ampliconlængde, primerlængde (mellem 17 og 21 nukleotider) og måldomæne (bakterier eller Universal).,degenererede primerpar konverteres til ikke-degenererede primer-set-par og tilføjes til et arkiv. Den procedure, så iterates nrest gange, hver gang en tilfældig prøvetagning primer-sæt-par pstart fra Pareto-fronten og en tilfældig vektor α af den relative vægte for optimering score, med vægte, der er i stikprøven, ensartet fra den enhed simplex; den procedure, så løser en scalarization af multi-mål problemet, nemlig et enkelt-objektiv problem, som en lineær kombination af de tre mål med de relative vægte α er maksimeret, og tilføjer det resultat, at arkivet., Til dette formål normaliseres effektivitet, dækning og matchende bias-score til deres maksimum, så hver normaliseret score varierer mellem 0 og 1, og matchende bias omdefineres som 1-matchende bias, så den kan maksimeres som de andre scoringer., amplikon længde i rangeamplen
2 Tilføj til arkiv tilsvarende ikke-degenererede primer-sæt-par
3 for r = 1 til nrest
4 pf = PARETO-FRONTEN(arkiv)
5 Prøve pstart fra pf
6 Prøve α fra 3, med Σi ai = 1
7 p = LOCAL SEARCH(pstart , α , repset)
8 Tilføj s til arkivet
9 vende tilbage arkiv
Enkelt-objektiv optimering er opnået ved hjælp af den Bedste Forbedring Local Search algoritme : start fra en indledende primer-sæt-par, LOCAL-SEARCH algoritme cykler gennem de primere, for par og for hver primer, scanninger sit nabolag, jeg.,e. sæt af alle mulige lokale forstyrrelser af primeren. Lokale forstyrrelser består i alle mulige flips af et nukleotid (vurdering af de tre andre mulige baser) og alle mulige tilføjelser og fjernelser af et nukleotid i ekstremiteterne., Søgning i løsningen rum er udført med de bedste forbedring lokal søgning fremgangsmåde: efter at generere hele kvarteret, som forklaret ovenfor, den algoritme, der vælger den bedste nabo forstyrrelse, begynder det at generere den næste kvarter, og iterates, indtil det når frem til en løsning, hvor der ikke bedre nabo forstyrrelser kan findes. Proceduren afsluttes, når der ikke kan anvendes yderligere lokale forbedringer på nogen primer i primer-set-parret., Den vægtede SCORE-funktion beregner de tre optimeringsresultater fra et primer-set-par og det repræsentative sæt, multiplicerer scoringerne med de relative vægte α og returnerer summen af resultaterne.
Vi har udviklet et software-værktøj, implementere vores tilgang og frigivet under GNU General Public Licence, som mopo16S software værktøj (Multi-Mål Primer Optimering til 16 forsøg) ved http://sysbiobig.dei.unipd.it/?q=Software#mopo16S., mopo16S implementeres som et multithreading C++ kommandolinjeværktøj; soft .areværktøjet er afhængig af de effektive algoritmer og datastrukturer fra Se .an-biblioteket og bruger openMP-biblioteket til multithreading.,>
4 for i = 1 til |pcurr|
5 pri = i-th primer af pcurr
6 for pnew = pcurr med alle mulige tilføjelser og optag af en base på ekstremiteter og udskiftninger af en base af pri
7 scorenew = VÆGTEDE SCORE(pnew , α , repset)
8 hvis scorenew > scorebest
9 pbest = pnew
10 scorebest = scorenew
11 pcurr = pbest
12 tilbage pcurr
State-of-the-art primer par indledende løsninger
Vi valgte den online database probeBase som en kilde til kandidat primer-sæt-par til at blive brugt som indledende løsninger, som mopo16S., Databasen indeholder mere end 500 par (eventuelt degenererede) primere og rapporter for hver primer sin sekvens, strand og position, hvor det passer reference 16S Escherichia coli genet, og målet domæne, som den er udviklet (enten Bakterier, Archaea eller Universel).,
i Betragtning af det ønskede område for target amplicon længde som input af mopo16S, valgte vi alle primer par fra probeBase database, der opfylder alle følgende egenskaber:
-
Amplikon længde i det ønskede interval;
-
Længde af både primere, der er større end eller lig med 17 nt og mindre end eller lig med 21 nt;
-
Bakterier eller Universelt target domain af både primere.,
Da vores tilgang er at arbejde med sæt af ikke-degenererede primere, i tilfælde af degeneracies i enten frem eller omvendt primer, vi erstatte den degenererede primer med et tilsvarende sæt af ikke-degenererede primere, der er opnået ved at tildele alle mulige kombinationer af værdier til den degenererede nukleotider i primer. Et eksempel på denne procedure er angivet i tabel 1.
Vi beregnede de tre scoringer for hvert af primer-set-parene og identificerede blandt disse primer-set-parene, der danner den oprindelige Pareto-front.