Fylogenetiska nätverk ger ett sätt att beskriva och visualisera evolutionär historia som har genomgått så kallade reticulate evolutionära händelser såsom rekombination, hybridisering eller horisontell genöverföring. Nivån k i ett nätverk avgör hur icke-trädliknande evolutionen kan vara, med nivå 0 nätverk som träd. Vi studerar problemet med att bygga nivå-k fylogenetiska nätverk från trillingar, d.v.s. Fylogenetiska träd för tre blad (taxa). Vi ger, för varje k, ett nivåk-nätverk som är unikt definierat av sina trillingar. Vi demonstrerar tillämpligheten av detta resultat genom att använda det för att bevisa att (1) för alla k ≥ 1 är det NP-hårdt att konstruera ett nivå-k-nätverk som överensstämmer med alla indatatrilletter, och (2) för alla k ≥ 0 är det NP-hårdt att konstruera ett nivå-k-nätverk som överensstämmer med ett maximalt antal indatatrilletter, även när indatan är tät. Som ett svar på denna intractability ger vi en exakt algoritm för att bygga nivå-1 nätverk som överensstämmer med ett maximalt antal indata trillingar.
Senare, Van Iersel et al. REF visade att MaxRTC är NP-hård, även om den ingående tripletten är tät.
Uniqueness, intractability and exact algorithms: reflections on level-k phylogenetic networks
{'venue': None, 'journal': 'arXiv: Populations and Evolution', 'mag_field_of_study': ['Mathematics', 'Biology', 'Computer Science', 'Medicine', 'Physics']}