PMID- 17237080
OWN - NLM
STAT- MEDLINE
DCOM- 20070306
LR  - 20091104
IS  - 1367-4811 (Electronic)
IS  - 1367-4803 (Linking)
VI  - 23
IP  - 2
DP  - 2007 Jan 15
TI  - Using median sets for inferring phylogenetic trees.
PG  - e129-35
AB  - MOTIVATION: Algorithms for phylogenetic tree reconstruction based on gene order 
      data typically repeatedly solve instances of the reversal median problem (RMP) 
      which is to find for three given gene orders a fourth gene order (called median) 
      with a minimal sum of reversal distances. All existing algorithms of this type 
      consider only one median for each RMP instance even when a large number of 
      medians exist. A careful selection of one of the medians might lead to better 
      phylogenetic trees. RESULTS: We propose a heuristic algorithm amGRP for solving 
      the multiple genome rearrangement problem (MGRP) by repeatedly solving instances 
      of the RMP taking all medians into account. Algorithm amGRP uses a 
      branch-and-bound method that branches over medians from a selected subset of all 
      medians for each RMP instance. Different heuristics for selecting the subsets 
      have been investigated. To show that the medians for RMP vary strongly with 
      respect to different properties that are likely to be relevant for phylogenetic 
      tree reconstruction, the set of all medians has been investigated for artificial 
      datasets and mitochondrial DNA (mtDNA) gene orders. Phylogenetic trees have been 
      computed for a large set of randomly generated gene orders and two sets of mtDNA 
      gene order data for different animal taxa with amGRP and with two standard 
      approaches for solving the MGRP (GRAPPA-DCM and MGR). The results show that amGRP 
      outperforms both other methods with respect to solution quality and computation 
      time on the test data. AVAILABILITY: The source code of amGRP, additional results 
      and the test instances used in this paper are freely available from the authors.
FAU - Bernt, Matthias
AU  - Bernt M
AD  - Parallel Computing and Complex Systems Group, Department of Computer Science, 
      University of Leipzig Augustusplatz 10/11, 04109 Leipzig, Germany.
FAU - Merkle, Daniel
AU  - Merkle D
FAU - Middendorf, Martin
AU  - Middendorf M
LA  - eng
PT  - Journal Article
PT  - Research Support, Non-U.S. Gov't
PL  - England
TA  - Bioinformatics
JT  - Bioinformatics (Oxford, England)
JID - 9808944
SB  - IM
MH  - *Algorithms
MH  - Chromosome Mapping/*methods
MH  - Conserved Sequence
MH  - Databases, Genetic
MH  - Evolution, Molecular
MH  - Gene Rearrangement/*genetics
MH  - Genome/*genetics
MH  - Linkage Disequilibrium/*genetics
MH  - *Phylogeny
MH  - Sequence Analysis, DNA/*methods
MH  - Sequence Homology, Nucleic Acid
EDAT- 2007/01/24 09:00
MHDA- 2007/03/07 09:00
CRDT- 2007/01/24 09:00
PHST- 2007/01/24 09:00 [pubmed]
PHST- 2007/03/07 09:00 [medline]
PHST- 2007/01/24 09:00 [entrez]
AID - 23/2/e129 [pii]
AID - 10.1093/bioinformatics/btl300 [doi]
PST - ppublish
SO  - Bioinformatics. 2007 Jan 15;23(2):e129-35. doi: 10.1093/bioinformatics/btl300.