Computing steiner minimum trees in Hamming metric

ABSTRACT

Computing Steiner minimum trees in Hamming metric is a well studied problem that has applications in several fields of science such as computational linguistics and computational biology. Among all methods for finding such trees, algorithms using variations of a branch and bound method developed by Penny and Hendy have been the fastest for more than 20 years. In this paper we describe a new pruning approach that is superior to previous methods and its implementation.

REFERENCES

• 1: E. Chare, E. Gould, and E. Holmes. Phylogenetic analysis reveals a low rate of homologous recombination in negative-sense rna viruses. J Gen Virol, 84, 2003.
• 2: Thomas T. Cormen , Charles E. Leiserson , Ronald L. Rivest, Introduction to algorithms, MIT Press, Cambridge, MA, 1990
• 3: Doratha E. Drake , Stefan Hougardy, A simple approximation algorithm for the weighted matching problem, Information Processing Letters, v.85 n.4, p.211-213, 28 February 2003 [doi>10.1016/S0020-0190(02)00393-9]
• 4: J. Felsenstein. PHYLIP (phylogeny inference package) version 3.6, 2004. Distributed by the author.
• 5: W. M. Fitch. Toward defining the course of evolution: minimum change for a specified tree topology. Systematic Zoology, 20, 1971.
• 6: L. Foulds and R. Graham. The Steiner problem in phylogeny is NP-complete. Advances in Applied Mathematics, 3, 1982.
• 7: M. D. Hendy and D. Penny. Branch and bound algorithms to determine minimal evolutionary trees. Mathematical Biosciences, 59, 1982.
• 8: B. R. Holland, K. T. Huber, D. Penny, and V. Moulton. The minmax squeeze: Guaranteeing a minimal tree for population data. Molecular Biology and Evolution, 22(2), 2005.
• 9: S. Kumar, K. Tamura, and M. Nei. Mega 3: Integrated software for molecular evolutionary genetics analysis and sequence alignment. Briefings in Bioinformatics, 5, 2004.
• 10: N. Nei and S. Kumar. Molecular Evolution and Phylogenetics. Oxford University Press, 2000.
• 11: T. Polzin. Algorithms for the Steiner Problem in Networks. PhD thesis, Universität des Saarlandes, 2003.
• 12: P. Purdom, P. Bradford, K. Tamura, and S. Kumar. Single column discrepancy and dynamic max-mini optimizations for quickly finding the most parsimonious evolutionary trees. Bioinformatics, 16, 2000.
• 13: A. Rambaut and N. Grassly. Seq-Gen: an application for the Monte Carlo simulation of DNA sequence evolution along phylogenetic trees. Comput. Appl. Biosci., 13, 1997.
• 14: V. Ranwez and O. Gascuel. Quartet based phylogenetic inference: improvement and limits. Molecular Biology and Evolution, 18, 2001. http://www.lirmm.fr/ranwez/.
• 15: A. Schrijver. Combinatorial optimization: polyhedra and efficiency. Springer, 2003.
• 16: M. Steel. Should phylogenetic models be trying to 'fit an elephant'? Trends in Genetics, 21(6), 2005.
• 17: D. L. Swofford. PAUP*. Phylogenetic Analysis Using Parsimony (*and other methods). Version 4., 2003.
• 18: D. M. Warme, P. Winter, and M. Zachariasen. Exact algorithms for plane steiner tree problems: A computational study. In Advances in Steiner Trees. Kluwer Academic Publishers, 2000.
• 19: Phylogeny programs. http://evolution.genetics.washington.edu/phylip/software.html.

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Counting problems

General Terms:
Algorithms, Theory