Vi betraktar problemet med att bygga ett artträd med tanke på ett antal genträd. I de ramar som införts av Goodman m.fl. [3], sidan [10], och Guig6, Muchnik och Smith [5] är formulerat som ett optimeringsproblem, nämligen att hitta arten träd som kräver det minsta antalet dubbleringar och / eller förluster för att förklara genträden. I detta dokument presenterar vi WIDTH k DUPLI-CATION-LOSS och WIDTH k DUPLICATION problem. Ett genträd har bredden k w.r.t, ett artträd, om arten trädet kan försonas med genträdet med hjälp av högst k samtidigt aktiva kopior av genen längs dess grenar. Vi förklarar w.r.t, till den underliggande biologiska modellen, varför denna bredd är typiskt mycket liten i jämförelse med det totala antalet dubbleringar och förluster. Vi visar polynom tid algoritmer för att hitta optimala arter träd som har avgränsad bredd w.r.t. minst ett av de ingående genträden. Dessutom presenterar vi den första algoritmen för ingångsgenträd som inte är rotade. Slutligen tillämpar vi våra algoritmer på en datauppsättning från [5] och visar ett artträd som kräver betydligt färre dubbleringar och färre dubbleringar/förluster än de träd som anges i det ursprungliga pappret.
REF presenterade en algoritm för att härleda arten träd från en uppsättning rotade genträd i polynom tid under begränsningen att arten träd kan förenas med genträdet med hjälp av som mest k samtidiga kopior av genen längs dess grenar.
New algorithms for the duplication-loss model
{'venue': "RECOMB '00", 'journal': None, 'mag_field_of_study': ['Mathematics', 'Computer Science']}