ABSTRACT Miljontals gener i den moderna arten tillhör endast tusentals genfamiljer. Gener duplicerar och går förlorade under evolutionen. En genfamilj omfattar fall av samma gen hos olika arter och duplicerade gener hos samma art. Två gener i olika arter är ortolog om deras gemensamma förfader ligger i den senaste gemensamma förfadern till arten. På grund av komplex gen evolutionär historia, ortolog identifiering är en grundläggande men svår uppgift i jämförande genomik. En viktig metod för uppgiften är att använda en explicit modell av den evolutionära historien om de gener som studeras, kallad genen (familjeträdet). Den jämför genträdet med den evolutionära historien om den art i vilken generna finns, kallad artträdet, med det förfarande som kallas trädförsoning. Att förena binär gen och specifika träd är enkelt. Avstämning av träd innebär dock svåra problem när trädslag inte är binära i praktiken. Här studeras godtycklig gen och arter trädavstämning i en binär förfiningsmodell. Resultat: Problemet med att förena gen- och artträd är bevisat NP-hårdt när artträd inte är binärt ens för dubbleringskostnaden. Vi presenterar sedan den första effektiva metoden för att förena ett icke-binärt genträd och ett icke-binärträd. Det försöker hitta en binär förfining av den givna genen och arter träd som minimerar den givna försoningskostnaden om de inte är binära. Våra algoritmer har implementerats i en programvara för att stödja snabb automatiserad analys av stora datamängder. Tillgänglighet: Programmet, tillsammans med källkoden, finns på sin onlineserver http://phylotoo.appspot.com.
Att hitta den lägsta kostnaden mellan ett rotat binärt genträd och alla binära förfiningar av ett rotat icke-binär art träd är däremot NP hård REF.
Reconciliation of Gene and Species Trees With Polytomies
{'venue': None, 'journal': 'arXiv: Populations and Evolution', 'mag_field_of_study': ['Biology']}