de.mpg.escidoc.pubman.appbase.FacesBean
Deutsch
 
Hilfe Wegweiser Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Buchkapitel

An Improved Algorithm for the Macro-evolutionary Phylogeny Problem

MPG-Autoren

Behzadi,  Behshad
Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons50613

Vingron,  Martin
Gene regulation (Martin Vingron), Dept. of Computational Molecular Biology (Head: Martin Vingron), Max Planck Institute for Molecular Genetics, Max Planck Society;

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

Behzadi, B., & Vingron, M. (2006). An Improved Algorithm for the Macro-evolutionary Phylogeny Problem. In Combinatorial Pattern Matching (pp. 177-187). Berlin/Heidelberg: Springer.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0010-84E8-7
Zusammenfassung
Macro-evolutionary processes (e.g., gene duplication and loss) have rarely been incorporated into gene phylogeny reconstruction methods. Durand et al. [5] have proposed a polynomial time dynamic programming algorithm to find the gene family tree that optimizes a macro-evolutionary criterion which is the weighted sum of the number of gene duplications and losses. The complexity of this algorithm is O(nm2) where n is the number of species and m is the maximum number of copies of the gene in a species. In this paper, we propose an improved algorithm with time complexity of O(nm) for solving this problem. We also show, that the problem can be solved in O(n) if unit costs are considered for both loss and duplication.