Format

Send to

Choose Destination
See comment in PubMed Commons below
J Comput Biol. 2006 Oct;13(8):1397-418.

On the repeat-annotated phylogenetic tree reconstruction problem.

Author information

1
Department of Computer Science, Technion-Israel Institute of Technology, Haifa, Israel. swidanf@janelia.hhmi.org

Abstract

A new problem in phylogenetic inference is presented, based on recent biological findings indicating a strong association between reversals (i.e., inversions) and repeats. These biological findings are formalized here in a new mathematical model, called repeat-annotated phylogenetic trees (RAPT). We show that, under RAPT, the evolutionary process--including both the tree-topology as well as internal node genome orders--is uniquely determined, a property that is of major significance both in theory and in practice. Furthermore, the repeats are employed to provide linear-time algorithms for reconstructing both the genomic orders and the phylogeny, which are NP-hard problems under the classical model of sorting by reversals (SBR).

PMID:
17061918
DOI:
10.1089/cmb.2006.13.1397
[Indexed for MEDLINE]
PubMed Commons home

PubMed Commons

0 comments

    Supplemental Content

    Full text links

    Icon for Mary Ann Liebert, Inc.
    Loading ...
    Support Center