title: Live phylogeny.
abstract: The live phylogeny problem generalizes the phylogeny problem while admitting the existence of living ancestors among the taxonomic objects. This problem suits the case of fast-evolving species, like virus, and the construction of phylogenies for nonbiological objects like documents, images, and database records. In this article, we formalize the live phylogeny problem for distances and character states and introduce polynomial-time algorithms for particular versions of the problems. We believe that more general versions of the problems are NP-hard and that many heuristic and approximation approaches may be developed as solution strategies.
authors.affiliation: Institute of Computing, University of Campinas, Campinas, Brazil. gpt@ic.unicamp.br
authors.forename: Guilherme P
authors.initials: GP
authors.lastname: Telles
authors.forename: Nalvo F
authors.initials: NF
authors.lastname: Almeida
authors.forename: Rosane
authors.initials: R
authors.lastname: Minghim
authors.forename: Maria Emilia M T
authors.initials: ME
authors.lastname: Walter
mesh_terms: D000465:Algorithms; D019295:Computational Biology; D019143:Evolution, Molecular; D055641:Mathematical Concepts; D010802:Phylogeny