I ett seminalpapper från 1997 föreslog W. Maddison att man skulle minimera djupa kolescenser, eller MDC, som ett optimeringskriterium för att härleda artträdet från en uppsättning inkongruenta genträd, förutsatt att inkongruensen uteslutande beror på linjesortering. I en efterföljande tidning, Maddison och Knowles gav och genomförde en sökning heuristic för att optimera MDC-kriteriet, med tanke på en uppsättning gen träd. Den heuristiska är dock inte garanterad att beräkna optimala lösningar, och dess hillclimbing sökning gör det långsamt i praktiken. I detta dokument ger vi två exakta lösningar på problemet med att härleda arten träd från en uppsättning genträd enligt MDC-kriteriet. Med andra ord, våra lösningar är garanterade att hitta trädet som minimerar det totala antalet djupa kolescenser från en uppsättning av genträd. En lösning är baserad på ett nytt heltal linjär programmering (ILP) formulering, och en annan bygger på en enkel dynamisk programmering (DP) metod. Kraftfulla ILP-lösare, såsom CPLEX, gör den första lösningen tilltalande, särskilt för mycket storskaliga fall av problemet, medan den DP-baserade lösningen eliminerar beroendet av egna verktyg, och dess enkelhet gör det enkelt att integrera med andra genomiska händelser som kan orsaka genträd inkongruens. Med hjälp av de exakta lösningarna analyserar vi en datamängd på 106 loci från åtta jästarter, en datamängd på 268 loci från åtta Apicomplexanarter och flera simulerade datamängder. Vi visar att MDC-kriteriet ger mycket exakta uppskattningar av arten trädtopologier, och att våra lösningar är mycket snabba, vilket möjliggör en korrekt analys av genomskala datamängder. Dessutom möjliggör lösningarnas effektivitet en snabb undersökning av suboptimala lösningar, vilket är viktigt för ett parsimoniskt kriterium som MDC, som vi visar. Vi visar att det i praktiken kan räcka med att söka efter artträdet i kompatibilitetsdiagrammet för de kluster som induceras av genträden, ett fynd som bidrar till att förbättra beräkningskraven för optimeringslösningar. Vidare undersöker vi den statistiska konsekvensen och konvergensen i MDC-kriteriet, liksom dess optimala tillvägagångssätt när det gäller att härleda artträdet. Slutligen visar vi hur våra lösningar kan användas för att identifiera potentiella horisontella genöverföringshändelser som kan ha orsakat en del av inkongruensen i data, vilket förstärker Maddisons ursprungliga ramverk. Vi har implementerat våra lösningar i PhyloNets programvarupaket, som är fritt tillgängligt på: http://bioinfo.cs.rice.edu/phylonet.
Mest liknande GD problem, ILP formuleringar har införts för djup kolescens problem, varianten av GTP problem där försoningskostnaden bygger på den djupa kolescens händelser REF.
Species Tree Inference by Minimizing Deep Coalescences
{'venue': 'PLoS Computational Biology', 'journal': 'PLoS Computational Biology', 'mag_field_of_study': ['Medicine', 'Biology', 'Computer Science']}