Abstract
Eksisterende teknikker for å rekonstruere tre modeller av progresjon for akkumulerte prosesser, slik som kreft, søke å estimere årsakssammenheng ved å kombinere korrelasjon og en frequentist oppfatningen av tidsmessige prioritet. I denne artikkelen, definerer vi en ny teoretisk rammeverk kalt CAPRESE (kreft progresjon Extraction med Single Edges) for å rekonstruere slike modeller basert på tanken om sannsynlighetsårsaks definert av Suppes. Vi betrakter en generell rekonstruksjon innstilling kompliseres ved nærværet av støy i dataene på grunn av biologisk variasjon, i tillegg til eksperimentelle eller målefeil. For å bedre toleranse for støy vi definere og bruke en krymping lignende estimator. Vi bevise riktigheten av vår algoritmen ved å vise asymptotisk konvergens til den riktige treet under milde begrensninger på nivået av støy. Videre på syntetiske data, viser vi at vår tilnærming utkonkurrerer state-of-the-art, at det er effektiv selv med et relativt lite antall prøver og at ytelsen konvergerer raskt til sin asymptote som antall prøver øker. For virkelige kreft datasett oppnådd med forskjellige teknologier, merker vi biologisk signifikante forskjeller i progresjoner inferred med hensyn til andre konkurrerende teknikker og vi viser også hvordan å validere antatt biologiske relasjoner med progresjonsmodeller
Citation. Loohuis LO, Caravagna G, Graudenzi A, Ramazzotti D, Mauri G, Antoniotti M, et al. (2014) konkludere Tre Årsaks modeller av kreft progresjon med sannsynlighets Heving. PLoS ONE 9 (10): e108358. doi: 10,1371 /journal.pone.0108358
Redaktør: Lars Kaderali, Technische Universität Dresden, Medisinsk fakultet, Tyskland
mottatt: 11 april 2014; Godkjent: 27 august 2014; Publisert: 09.10.2014
Copyright: © 2014 Olde Loohuis et al. Dette er en åpen-tilgang artikkelen distribueres under betingelsene i Creative Commons Attribution License, som tillater ubegrenset bruk, distribusjon og reproduksjon i ethvert medium, forutsatt den opprinnelige forfatteren og kilden krediteres
Data Tilgjengelighet:. Den forfatterne bekrefter at alle data som underbygger funnene er fullt tilgjengelig uten restriksjoner. Alle data er inkludert i papir
Finansiering:. Dette arbeidet ble støttet av National Science Foundation bevilger CCF-0836649 og CCF-0926166 og av Regione Lombardia (Italia) under forskningsprosjekter RetroNet gjennom Astil [12 -4-5148000-40]; UA 053 og nedd Prosjekt [ID14546A Rif SAL-7] Fondo Accordi Istituzionali 2009. finansiører hadde noen rolle i studiedesign, datainnsamling og analyse, beslutning om å publisere, eller utarbeidelse av manuskriptet
Konkurrerende interesser.: forfatterne har erklært at ingen konkurrerende interesser eksisterer.
Innledning
Kreft er en sykdom av evolusjon. Dens initiering og progresjon er forårsaket av dynamiske somatiske forandringer i genomet manifestert som punktmutasjoner, strukturelle forandringer, DNA-metylering og histon-modifikasjonsendringer [1].
Disse genomiske forandringer frembringes av tilfeldige prosesser, og siden individuelle tumor celler konkurrere om plass og ressurser, er de sprekeste varianter naturlig utvalgt for. Hvis for eksempel gjennom noen mutasjoner en celle får evnen til å ignorere anti-vekstsignaler fra kroppen, kan denne celle trives og dividere og dens avkom kan til slutt dominere noen del (er) av tumoren. Dette
klonal ekspansjon
kan sees som en
diskret tilstand
av kreft progresjon, preget av oppkjøpet av et sett av genetiske hendelser. Progresjon av kreft kan da betraktes som en sekvens av disse diskrete trinn, hvor tumoren overtar visse distinkte egenskaper ved hver tilstand. Ulike progresjon sekvenser er mulig, men noen er mer vanlig enn andre, og ikke hver bestilling er levedyktig [2].
I de siste to tiårene, mange spesifikke gener og genetiske mekanismene som er involvert i ulike typer kreft Det er identifisert (se f.eks [3], [4] for en oversikt over vanlige kreftgener og [5], [6] for spesifikke genetiske analyser av ovarialcancer og lunge adenokarsinom, henholdsvis), og
terapier
rettet mot aktiviteten til disse genene er nå under utvikling i et raskt tempo [2]. Men, dessverre,
årsaks og tidsmessige relasjoner
blant de genetiske hendelser kjøre kreft progresjon fortsatt i stor grad unnvikende.
Hovedårsaken til denne situasjonen er at informasjonen avslørt i data oppnås vanligvis bare på ett (eller et par) punkter i tid, i stedet for i løpet av sykdommen. Ekstrahering av dette dynamisk informasjon fra den tilgjengelige
tverrsnitts
data er krevende, og en kombinasjon av matematiske, statistiske og beregningsteknikker er nødvendig. I de siste årene har flere metoder trekke progresjon modeller fra tverrsnittsdata har blitt utviklet, fra banebrytende arbeid på single-bane-modeller av Fearon og Vogel [7]. Spesielt ble forskjellige modeller av oncogenetic trær utviklet seg gjennom årene. I kjernen av noen av disse metodene, f.eks [8], [9], er bruken av
korrelasjon
å identifisere relasjoner mellom genetiske hendelser. Disse teknikkene rekonstruere
tre
modeller av progresjon som selvstendige asykliske baner med grener og ingen Confluences. Distinkte modeller av oncogenetic trær er i stedet basert på
maximum likelihood estimering
, f.eks [10], [11], [12]. Mer generelle
Markov kjede
modeller, for eksempel [13], beskrive mer fleksibel sannsynlighets nettverk, til tross for beregningsmessig dyrt parameterestimering. Andre nyere modeller er konjunktiv Bayesian Networks, CBNs [14], [15], at ekstrakt
rettet asykliske grafer
, ennå pålegg om særskilte begrensninger på felles forekomst av hendelser. Til slutt, i en litt annen sammenheng, ble time modeller rekonstruert fra tid-retters genuttrykk data [16], [17].
I denne artikkelen presenterer vi en ny teoretisk rammeverk kalt CAPRESE (kreft progresjon Extraction med Single Edges) til å rekonstruere kumulative progressive fenomener, som kreft progresjon. Vi antar det opprinnelige problemet innstillingen av [8], og foreslå en ny en teknikk for å antyde
sannsynlighets progresjon trær
fra tverrsnittsdata. I motsetning til maksimum likelihood estimering-baserte teknikker, er vårt mål utvinning av
minimal
progresjon modell som forklarer den rekkefølgen mutasjoner oppstår og akkumulere. Metoden er teknologi agnostiker, dvs, kan det brukes til datasett avledet fra alle typer (epi-) genetiske data som dyp exome sekvensering, bisulfite sekvensering, SNP arrays, etc., (se resultater), og tar som input en . sett med forhånds utvalgte genetiske hendelser som tilstedeværelse eller fravær av hver hendelse er registrert for hver prøve
CAPRESE er basert på to hovedingredienser: istedenfor å bruke
korrelasjon
å antyde progresjon strukturer, baserer vi vår teknikk på en forestilling om
sannsynlighetsårsaks
, og for å øke robustheten mot støy, vi vedta en
krymping lignende estimator
å måle årsakssammenheng mellom ethvert par av hendelser. Mer spesifikt med hensyn til vår første ingrediens, vedta vi begrepet (prima facie) årsaksforeslått av Suppes i [18]. Dens grunnleggende intuisjon er enkel: hendelse forårsaker hendelse hvis det oppstår
før
og forekomsten av
øker sannsynligheten
for å observere. Dette er en svært grunnleggende forestilling om sannsynlighetsårsakssammenheng som i seg selv ikke løser mange av problemene knyttet til det (for eksempel asymmetri, vanlige årsaker, og screening av [19]), og inkluderer
falsk
samt
ekte
årsaker. Men, som det viser seg, denne grunnleggende oppfatningen kombinert med et filter for uavhengige progresjoner start fra samme rot, er et utmerket verktøy for å lede utviklingen utvinning fra tverrsnittsdata -. En som utkonkurrerer de mest brukte korrelasjonsbaserte metoder
Probabilistic kausalitet ble brukt i biomedisinske applikasjoner før (for eksempel for å finne driver gener fra CNV data i [20], og å trekke ut årsaker fra biologiske tidsseriedata i [21]), men til vår beste kunnskap aldri å antyde
progresjonsmodeller
i
fravær
direkte timelig informasjon.
utvinning problemet er komplisert av tilstedeværelsen av både falske positive og falske negative observasjoner (se [22] for en diskusjon om dette problemet basert på gjenoppbyggingen av [8]), slik som den som leveres av den iboende variasjon av biologiske prosesser (f.eks,
genetisk heterogenitet
) og
eksperimentelle feil
. Dette utgjør et problem, fordi mens sannsynligheten hevingen er en veldig presis verktøy, det i seg selv er ikke robust nok mot støy. Betinget av hvor mye støy, vil vi stole både på probabilistiske årsakssammenheng og på en mer robust (men mindre presis) korrelasjon-basert beregning på en optimal måte. For å gjøre dette vi presentere vår andre ingrediens, en
krymping lignende estimator
å måle årsakssammenheng mellom ethvert par av hendelser. Den intuisjon bak denne estimator, som er nært beslektet med en krymping estimator fra [23], er å finne den optimale balansen mellom sannsynlighet høyne på den ene side og korrelasjon på den andre, avhengig av mengden av støy.
Vi bevise riktigheten av vår algoritme ved å vise at med økende utvalgsstørrelser, den rekonstruerte treet asymptotisk konvergerer til den riktige (sats 3). Under milde begrensninger på støy priser, har dette resultatet for gjenoppbyggingen problem i nærvær av uniform støy også.
Vi har også studere resultatene av CAPRESE i mer realistiske innstillinger med begrensede utvalgsstørrelser. Ved hjelp av syntetiske data, viser vi at under disse forholdene, utkonkurrerer vår algoritme state-of-the-art tre rekonstruksjon algoritme av [8] (se resultater). Spesielt vår svinn-lignende estimator gir i gjennomsnitt en økt robusthet for støy som sikrer det å utkonkurrere oncotrees [8]. Ytelsen er definert i form av
strukturell likhet
mellom den rekonstruerte treet og selve treet i stedet for på sin indusert fordeling som er gjort, for eksempel, i [11]. Denne beregningen er spesielt egnet for målet om å rekonstruere en progresjon modell der data-sannsynligheten fit er sekundært til «kaller» det muligens minimalt sett med årsakssammenhenger.
Dessuten viser vi at CAPRESE fungerer godt allerede med en relativt lavt antall prøver, og at ytelsen konvergerer raskt til sin asymptoten som antall prøver øker. Dette utfallet hint på anvendelsen av algoritmen med relativt små datasett uten å kompromittere sin effektivitet.
Vi bemerke at videre analyser på syntetiske data tyder på at CAPRESE utkonkurrerer en velkjent bayesiansk sannsynlighets grafisk modell i tillegg (dvs.
bindehinnen Bayesian Networks product: [14], [15]), som opprinnelig ble unnfanget for gjenoppbyggingen av mer komplekse topologier, f.eks Dags, men ble vist seg effektive i å rekonstruere tre topologier samt [24] (se resultater).
Til slutt, bruker vi vår teknikk til endringer vurderes med både komparativ genomisk hybridisering og Next Generation Sekvense teknikker (se resultater). I det første tilfellet, viser vi at algoritmen av [8] og CAPRESE høydepunkt biologisk viktige forskjeller i eggstokkene, gastrointestinale og kreft i munnhulen, men våre slutninger er statistisk mer betydelig. I sistnevnte, validere vi en nylig oppdaget forhold mellom to viktige gener involvert i leukemi.
Metoder
Problem sette
Oppsettet av gjenoppbygging problemet er som følger . Forutsatt at vi har et sett av mutasjoner (
hendelser
, i sannsynlighets terminologi) og prøver, representerer vi et tverrsnitt datasett som en binær matrise der en oppføring hvis mutasjonen ble observert i prøven, og ellers. Problemet vi løser i denne artikkelen er å trekke ut et sett med kanter som ga en progresjon
tre
fra denne matrisen som vi bemerke, gir bare implisitt informasjon om progresjon timing. Roten av er modellert ved hjelp av en (spesiell) hendelse slike som
heterogene progresjon stier
eller
skoger
kan rekonstrueres. Mer presist, tar vi sikte på å rekonstruere en
forankret tre
som tilfredsstiller: hver node har maksimalt en innkommende kant, har rot ingen innkommende kanter er det ingen
sykluser Book
Hver progresjon tre subsumes en fordeling for å observere en undergruppe av mutasjoner i en kreftprøve som kan formaliseres som følger:
Definition 1. (tre-indusert distribusjon)
La
være et tre og Selge
en merking funksjon betegner den uavhengige sannsynligheten for hver kant, etter
genererer en fordeling hvor sannsynligheten for å observere en prøve med et sett av endringer
er
(1)
hvor alle hendelser i
antas å være tilgjengelig fra roten
, og Selge
er det sett av kanter koble roten til hendelsene i
.
Vi ønsker å understreke to eiendommer knyttet til treet-indusert distribusjon. Først subsumes fordeling at, gitt en hvilken som helst orientert kant, inneholder en prøve observert endring med sannsynlighet, som er sannsynligheten for å observere etter. Av denne grunn, hvis årsaker, vil sannsynligheten for å observere være større enn sannsynligheten for å observere i henhold til den tidsmessige prioritet prinsipp som sier at alle årsaker må komme foran i tid, deres effekter [25].
For det andre, inngangsdatasettet er et sett av prøver generert, ideelt sett, fra en ukjent fordeling indusert av en ukjent tre eller skog som vi tar sikte på Rekonstruer. Men i noen tilfeller kan det være at det ikke finnes tre hvis indusert distribusjon genererer
nøyaktig
disse inngangsdata. Når dette skjer, det sett av observerte prøver noe avviker fra noe tre-indusert distribusjon. For å modellere disse situasjonene en forestilling om
støy
kan innføres, som avhenger av i hvilken sammenheng data er samlet. Legge til støy i modellen kompliserer rekonstruksjon problemet (se resultater).
oncotree
tilnærming.
I [8] Desper
et al.
utviklet en metode for å utvinne progresjon trær, heter
«oncotrees»
, fra statiske CNV data. I [22] Szabo
et al. Extended innstillingen av Desper gjenoppbygging problem å ta høyde for både
falske positiver
og
negativer
i inndata. I disse oncotrees, nodene representerer CNV hendelser og kanter tilsvarer mulige progresjoner fra en hendelse til den neste.
rekonstruksjon problemet er nøyaktig som beskrevet ovenfor, og hvert tre er forankret i den spesielle hendelsen. Valget av hvilken kant for å inkludere i et tre er basert på estimator (2) som tildeler hver kant en vekt regnskap for både de relative og felles frekvenser av hendelsene – og dermed måle
korrelasjon
. Estimatoren evalueres etter herunder til hver prøve av datasettet. I denne definisjonen helt til høyre sikt er det (symmetrisk)
likelihood ratio
for og forekommer sammen, mens lengst til venstre er den asymmetriske
temp prioritet
målt ved frekvensen av forekomsten. Dette implisitt form for timing forutsetter at dersom det oppstår
oftere
enn, så er det sannsynlig at det oppstår
tidligere
, og dermed tilfredsstillende
En oncotree er forankret tre hvis totalvekten ( det vil si summen av alle vekter av kantene) er maksimert, og kan rekonstrueres i trinn med Edmond algoritme [26]. Ved bygging, er den resulterende grafen en skikkelig tre forankret i: hver hendelse inntreffer bare en gang,
Confluences
er fraværende, dvs. enhver hendelse er forårsaket av høyst en annen hendelse. Denne fremgangsmåten har blitt brukt til å utlede progresjon for ulike kreft datasett f.eks, [27], [28], [29]), og selv om flere metoder som strekker denne ramme finnes (f.eks [9], [11], [15] ), til det beste av vår kunnskap, er det i dag den eneste metoden som tar sikte på å løse akkurat det samme problemet som den undersøkt i denne utredningen, og dermed gi en målestokk å sammenligne mot.
en probabilistisk tilnærming til årsakssammenheng
Vi kort gjennomgå tilnærming til probabilistiske årsakssammenheng, som vår metode er basert på. For en omfattende diskusjon om dette temaet vi se [19].
I sitt banebrytende arbeid [18], Suppes foreslått følgende forestillingen.
Definition 2. (Probabilistic årsakssammenheng, [18] ).
For eventuelle to hendelsene
og Selge
, som forekommer henholdsvis til tider
og Selge
, under milde forutsetninger som
, er hendelsen
en prima facie årsaken til hendelsen
hvis det skjer før effekten og årsaken øker sannsynligheten for effekt, det vil si, etter (3)
som omtalt i [19] ovennevnte vilkår ikke er generelt tilstrekkelig til å hevde at hendelsen er en årsak til hendelsen. Faktisk en prima facie sak er enten
ekte
eller
falsk
. I det sistnevnte tilfelle, det faktum at betingelsene hold i observasjonene skyldes enten tilfeldig eller i nærvær av en viss tredje
problemfaktor
, relatert både til og til [18]. Ekte årsaker, i stedet, tilfreds Definisjon 2 og er ikke skjermet av med en problemfaktor. Men de trenger ikke være direkte årsaker. Se figur 1.
Eksempel prima facie topologi der alle kanter representere prima facie årsaker, ifølge Definisjon 3: er en sannsynlighet raiser av og det skjer oftere. I venstre, filtrerer vi ut falske årsaker og velger bare de ekte blant de ekte, noe som gir en enkelt årsak prima facie topologi.
Legg merke til at vi anser tverrsnittsdata der ingen informasjon om og er tilgjengelig, så i vår rekonstruksjon innstillingen vi er begrenset til å vurdere utelukkende på
sannsynlighet øke plakater (PR) eiendom, det vil si, noe som gjør det vanskeligere å diskriminere mellom ekte og falske årsaker. Nå vurderer vi noen av sine eiendommer.
Proposition 1. (Avhengighet).
Når
PR
har mellom to hendelser
og Selge
, deretter hendelsene er
statistisk avhengige
i positiv forstand, dvs.
(4)
Denne og neste forslag er velkjente fakta av PR; deres avledning samt bevis på alle resultatene vi presenterer er i File S1. Legg merke til at det motsatte implikasjonen holder også: når hendelser og er fortsatt avhengig, men i negativ forstand, det vil si, ikke PR ikke holde, det vil si, etter
Vi ønsker å bruke asymmetri av PR. for å avgjøre om et par av hendelser og tilfredsstille en årsakssammenheng forhold så til sted før i progresjonen treet, men, dessverre, PR tilfredsstiller følgende egenskap.
Proposition 2. (Mutual PR). .
Det vil si, hvis øker sannsynligheten for å observere, hever så sannsynligheten for å observere også.
Likevel, for å kunne fastslå årsakene og virkningene av de genetiske hendelser, kan vi bruke vår
grad av tillit
i vårt anslag av sannsynlighet heve å bestemme retningen på årsaksforholdet mellom par av hendelser. Med andre ord, hever dersom sannsynligheten for
mer
enn den andre veien rundt, så er en mer sannsynlig årsak til enn av. Legg merke til at dette er høres så lenge hver hendelse har
høyst
en sak; ellers,
hyppige sene hendelser
med mer enn en årsak, som er ganske vanlig i biologisk progressiv fenomener, bør behandles på en annen måte. Som nevnt, er PR ikke symmetrisk, og
retning
sannsynlighets hevingen avhenger av relative frekvenser av hendelsene. Vi gjør denne asymmetrien presise i følgende proposisjoner.
Proposition 3. (Probability heving og tidsmessig prioritet).
For eventuelle to hendelsene
og Selge
slik at sannsynligheten hevingen
holder, har vi product: (5)
Det vil si, gitt at PR holder mellom to hendelser, øker sannsynligheten for
mer enn
øker sannsynligheten for, hvis og bare hvis det observeres oftere enn. Legg merke til at vi bruker forholdet til å vurdere PR ulikhet. Beviset for dette forslaget er teknisk og kan bli funnet på Fil S1. Fra dette resultat følger det at hvis vi måle tidspunktet for en hendelse av frekvensen av forekomsten (det vil si, innebærer det skjer før), denne oppfatningen av PR subsumes den samme oppfatningen av tidsmessige prioritet indusert av et tre. Vi bemerke også at dette er også tidsmessig prioritet gjort eksplisitt i koeffisientene Desper metode. Gitt disse resultatene, definerer vi følgende forestillingen om årsakssammenheng.
Definisjon 3.
Vi sier at
er en prima facie årsak til
hvis
er en sannsynlighet raiser av
, og det skjer oftere:
Vi term
prima facie topologi
en rettet asyklisk graf (over noen hendelser) hvor hver kant representerer en prima facie sak. Når høyst ett innkommende kant er tildelt hver hendelse (dvs. et arrangement har kun en
unik sak
, i den virkelige verden), kaller vi denne strukturen
én årsak prima facie topologi
. Intuitivt denne siste klassen av topologier tilsvarer trærne eller, mer generelt skoger når de har koblet komponenter, som vi tar sikte på å rekonstruere.
Før du går videre til å introdusere vår algoritme la oss diskutere vår definisjon av
kausalitet
, dens rolle i definisjonen av gjenoppbygging problemet og noen av sine begrensninger. Som allerede nevnt, kan det være at for noen påtakelig grunn av en hendelse, er det en tredje hendelse før begge deler, slik at årsaker og til slutt forårsaker. Alternativt kan føre til både og selvstendig, og årsaksforhold observert fra til er bare
falsk
. I sammenheng med den tre-rekonstruksjon problem, nemlig når det antas at hver hendelse har høyst en unik årsak, er målet å filtrere ut uønskede kantene fra en generell påtakelig topologi, så for å trekke ut en enkelt-sak påtakelig struktur (se figur 1).
Definisjon 3 oppsummerer Suppes grunnleggende oppfatningen av prima facie sak, mens det er ignorerer dypere diskusjoner om årsaks som tar sikte på å skille mellom faktiske ekte og falske årsaker, for eksempel screening-off, bakgrunn sammenheng, d-separasjons [30], [31], [19]. For vårt formål er imidlertid ovennevnte definisjon tilstrekkelig når alle de viktige hendelsene er vurdert, dvs. at alle ekte årsaker observert som i en lukket verden antagelse, og vi tar sikte på å trekke ut
For
av progresjonen blant dem (eller finne ut at det ikke er noen åpenbar sammenheng), i stedet for å trekke ut causalities
per se
. Merk at disse forutsetningene er sterke og kan bli svekket i fremtiden (se diskusjoner), men deles av oss og [8].
Til slutt husker vi noen algebraiske krav som er nødvendige for vårt rammeverk for å være godt definert. Først av alt må PR være Computable: hver mutasjon bør observeres med sannsynlighet strengt. Videre må vi hvert par av mutasjoner til å være
skjelnes
i form av PR, det vil si for hvert par av mutasjoner og, eller på samme måte som den ovennevnte betingelse. Enhver ikke-identifiserbar par av hendelser kan bli slått sammen som én hendelse. Fra nå av vil vi anta at disse vilkår som må verifiseres.
resultatmål og syntetiske datasett
Vi har gjort bruk av
syntetiske data
å evaluere ytelsen til CAPRESE som en funksjon av datasett størrelse og falske positive og negative priser. Mange forskjellige syntetiske datasett ble opprettet for dette formålet, som forklart nedenfor. Algoritmen resultater ble målt i
Tre Edit Avstand plakater (TED, [32]), dvs. minimum lige sekvens av node redigere operasjoner (relabeling, sletting og innsetting) som forvandler de rekonstruerte trær inn i som genererer data. Valget av dette tiltaket med evaluering er motivert av det faktum at vi er interessert i
struktur
bak progressive fenomenet kreft evolusjon og spesielt er vi interessert i et mål på ekte årsaker som vi savner og av de falske årsaker som vi ikke klarer å gjenkjenne (og fjerne). Også, siden topologier med liknende distribusjoner kan være strukturelt annerledes velger vi å måle ytelsen ved hjelp av strukturelle avstand heller enn en avstand i form av utbytte. Innenfor området for «strukturelle beregninger» Men vi har også evaluert ytelse med
Hamming Avstand product: [33], en annen vanlig brukt strukturelle beregning, og vi oppnådde analoge resultater (ikke vist her).
Syntetisk datagenerering og eksperimentell setting.
Syntetisk datasett ble generert av prøvetaking fra ulike tilfeldige trær begrenset til å ha dybde, siden brede grener er vanskeligere å rekonstruere enn rette stier, og ved prøvetaking hendelsessannsynligheter (se File S1).
med mindre eksplisitt spesifisert, i alle forsøkene vi brukt forskjellige tilfeldige trær (eller skog, i henhold til testen for å utføre) av hendelser hver. Dette virker en ganske rimelig antall hendelser og er på linje med den vanlige størrelse på rekonstruerte trær, f.eks [34], [35], [36], [37].
skalerbarhet
av teknikkene ble testet mot antall prøver av alt fra til, med et trinn av, og ved å kopiere uavhengige datasett for hver parameter innstilling (se bildeteksten av tallene for detaljer).
Vi inkluderte en form for
støy
i generering av datasett, for å ta hensyn til realistisk nærvær av
biologisk støy plakater (slik som den som tilbys av tilskuer mutasjoner, genetisk heterogenitet osv) og
eksperimentelle feil
. En støy parameter angir sannsynligheten for at enhver hendelse forutsetter en tilfeldig verdi (med uniform sannsynlighet), etter prøvetaking fra treet-indusert distribusjon. Algoritmer denne prosessen genererer i gjennomsnitt tilfeldige oppføringer i hver prøve (f.eks med vi har i gjennomsnitt én feil per prøve). Vi ønsker å vurdere om disse støyende prøvene kan villede gjenoppbyggingen, selv for lave verdier av. Legg merke til at anta en jevnt fordelt støy kan forekomme forenklede siden noen arrangementer kan være mer robust, eller lett å måle, enn andre. Men innføring i data både
falske positiver
(ved rate) og
negativer
(på rate) gjør slutning problem vesentlig hardere, og ble først undersøkt i [22].
i under resultatene, henviser vi til datasett generert med sats som støyende syntetisk datasett. I de numeriske eksperimenter, er vanligvis diskretisert av, (dvs. støy).
Resultater
Trekke progresjon trær med sannsynlighet heving og en krymping lignende estimator
CAPRESE rekonstruksjon metoden er beskrevet i algoritme 1. algoritmen er lik Desper og Szabo algoritme, den største forskjellen er et alternativ vekt funksjon basert på en krymping lignende estimator
algoritme 1. CAPRESE: a. trelignende rekonstruksjon med a. krymping lignende estimator
1: vurdere et sett av genetiske hendelser pluss en spesiell hendelse, lagt til hver prøve av datasettet,
2: definere en matrise der hver post inneholder krymping -liker estimator i henhold til den observerte sannsynligheten for hendelser og;
3: [PR årsaks] definerer et tre der for hvis og bare hvis:
4: [Uavhengig progresjoner filter] definere, erstatte kant med kanten hvis du for alt, det holder
Definisjon 4. (Svinn-lignende estimator).
Vi definerer
krymping lignende estimator
av tillit til årsaksforholdet fra
for bedriften
som plakater (6)
hvor
og plakater (7)
Dette estimator ligner i ånden til en krymping estimator (se [23]) og kombinerer en normalisert versjon av PR,
rå estimat
, med en
korreksjonsfaktor product: (i vårt tilfelle en sammenheng basert mål på tidsmessig avstand mellom hendelser), for å definere en riktig rekkefølge i tillit hver årsaksforhold. Vår er analog av
krymping koeffisient Hotell og kan ha en bayesiansk tolkning basert på styrken av vår tro på at og er årsaksmessig relevante for hverandre og bevisene som øker sannsynligheten for. I fravær av en lukket form løsning for den optimale verdi av, kan man stole på kryss-validering av simulerte data. Kraften av krymping (og vår krymping lignende estimator) ligger i muligheten til å bestemme en optimal verdi for å balansere effekten av korreksjonsfaktoren på den rå modell estimat, for å sikre optimale ytelser for syk utgjøres forekomster av slutning problem. En viktig forskjell er imidlertid mellom vår estimator og klassisk svinn, er at vår estimator tar sikte på å forbedre ytelsen til
generelle
gjenoppbyggingen, ikke begrenset til ytelsen til estimatoren seg selv som er tilfellet i krymping. Det vil si, det metriske induserer en bestilling til hendelser som reflekterer vår tillit til deres årsakssammenheng. Videre, siden vi gjør ingen antakelse om den underliggende distribusjon, lærer vi det empirisk ved kryssvalidering. I de neste avsnittene viser vi at krympingen lignende estimator er en effektiv måte å få en slik bestilling spesielt når data er støyende. I CAPRESE bruker vi en parvise matrise versjon av estimator.
Den rå estimator og korreksjonsfaktoren.
Ved å vurdere bare rå estimator, vi ville inkludere en kant i treet konsekvent når det gjelder av Definisjon 3 (Methods) og hvis er det beste sannsynligheten raiser for. Når hendelsene og er utvisket i form av time prioritet, er således ikke tilstrekkelig til å avgjøre deres årsaksforhold, hvis noen. Denne iboende tvetydighet er usannsynlig i praksis, selv om det i prinsippet er det mulig. Legg merke til at denne formuleringen av en monoton normalisert versjon av PR-forhold.
Proposition 4. (monoton normalisering).
For eventuelle to hendelsene
og Selge
har vi product: (8)
Denne rå modell estimator tilfreds: når det har en tendens til de to hendelsene vises disjointly (dvs. de viser en anti- årsaks mønster), når det har en tendens til ikke årsakssammenheng eller anti- årsakssammenheng kan utledes, og de to hendelsene er statistisk uavhengige, og, når det har en tendens til, den årsaksforholdet mellom de to hendelsene er ekte. Derfor gir en kvantifisering av graden av tillit for en PR årsaksforhold. Faktisk, for enhver mulig årsakssammenheng kant, begrepet gir et estimat på
feilrate
av, derfor telleren av rå modellen gir et anslag på hvor ofte er faktisk forårsaket av. Den estimator er så normalisert å ligge mellom og.
Men gir ikke en generell kriterium for å disambiguate blant ekte årsakene til en gitt hendelse. Vi viser en konkret sak der er ikke en tilstrekkelig estimator. La oss for eksempel en årsaks lineær sti. I dette tilfellet, når man skal vurdere kandidaten foreldre og for vi har: slik og er ekte årsaker til, selv om vi ønsker å velge, i stedet for. Følgelig kan vi bare antyde at og, det vil si en delvis bestilling, noe som ikke bidrar til å skille forholdet blant og med hensyn til.
I dette tilfelle koeffisient kan anvendes for å bestemme hvilke av de to ekte årsaker forekommer nærmere, i tid, for å (i eksemplet ovenfor). Generelt gir en korreksjonsfaktor informasjon om
temporal avstand
mellom hendelser, i form av statistisk avhengighet.
