An Ω(n^2/ log n) Speed-Up of TBR Heuristics for the Gene-Duplication Problem

ABSTRACT

The gene-duplication problem is to infer a species supertree from gene trees that are confounded by complex histories of gene duplications. This problem is NP-hard and thus requires efficient and effective heuristics. Existing heuristics perform a stepwise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. We improve on the time complexity of the local search problem by a factor of n2= log n, where n is the size of the resulting species supertree. Typically, several thousand instances of the local search problem are solved throughout a stepwise heuristic search. Hence, our improvement makes the gene-duplication problem much more tractable for large-scale phylogenetic analyses.

REFERENCES

• 1: R. Guigó, I. Muchnik, and T.F. Smith, "Reconstruction of Ancient Molecular Phylogeny," Molecular Phylogenetics and Evolution, vol. 6, no. 2, pp. 189-213, 1996.
• 2: Bin Ma , Ming Li , Louxin Zhang, On reconstructing species trees from gene trees in term of duplications and losses, Proceedings of the second annual international conference on Computational molecular biology, p.182-191, March 22-25, 1998, New York, New York, United States [doi>10.1145/279069.279113]
• 3: R.D.M. Page, "GeneTree: Comparing Gene and Species Phylogenies Using Reconciled Trees," Bioinformatics, vol. 14, no. 9, pp. 819-820, 1998.
• 4: J.B. Slowinski, A. Knight, and A.P. Rooney, "Inferring Species Trees from Gene Trees: A Phylogenetic Analysis of the Elapidae (Serpentes) Based on the Amino Acid Sequences of Venom Proteins," Molecular Phylogenetics and Evolution, vol. 8, no. 3, pp. 349-362, 1997.
• 5: R.D.M. Page, "Extracting Species Trees from Complex Gene Trees: Reconciled Trees and Vertebrate Phylogeny," Molecular Phylogenetics and Evolution, vol. 14, no. 1, pp. 89-106, 2000.
• 6: R.D.M. Page and J. Cotton, "Vertebrate Phylogenomics: Reconciled Trees and Gene Duplications," Proc. Seventh Pacific Symp. Biocomputing (PSB '02), R.B. Altman, A.K. Dunker, L. Hunter, K. Lauderdale and T.E. Klein, eds., pp. 536-547, Jan. 2002.
• 7: J.A. Cotton and R.D.M. Page, "Tangled Tales from Multiple Markers: Reconciling Conflict between Phylogenies to Build Molecular Supertrees," Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life, O.R.P. Bininda-Emonds, ed., pp. 107- 125, Springer, 2004.
• 8: M.J. Sanderson and M.M. McMahon, "Inferring Angiosperm Phylogeny from EST Data with Widespread Gene Duplication," BMC Evolutionary Biology, vol. 7, supplementary 1:S3, 2007.
• 9: D.L. Swofford, G.J. Olsen, P.J. Waddel, and D.M. Hillis, "Phylogenetic Inference," Molecular Systematics, D.M. Hillis, C. Moritz, and B.K. Mable, eds., chapter 11, pp. 407-509, Sinauer Assoc., 1996.
• 10: B.L. Allen and M. Steel, "Subtree Transfer Operations and Their Induced Metrics on Evolutionary Trees," Annals of Combinatorics, vol. 5, pp. 1-13, 2001.
• 11: D. Chen, O. Eulenstein, D. Fernández-Baca, and J.G. Burleigh, "Improved Heuristics for Minimum-Flip Supertree Construction," Evolutionary Bioinformatics, vol. 2, 2006.
• 12: M. Goodman, J. Czelusniak, G.W. Moore, A.E. Romero-Herrera, and G. Matsuda, "Fitting the Gene Lineage into Its Species Lineage. A Parsimony Strategy Illustrated by Cladograms Constructed from Globin Sequences," Systematic Zoology, vol. 28, pp. 132-163, 1979.
• 13: R.D.M. Page, "Maps between Trees and Cladistic Analysis of Historical Associations among Genes, Organisms, and Areas," Systematic Biology, vol. 43, no. 1, pp. 58-77, 1994.
• 14: B. Mirkin, I. Muchnik, and T.F. Smith, "A Biologically Consistent Model for Comparing Molecular Phylogenies," J. Computational Biology, vol. 2, no. 4, pp. 493-507, 1995.
• 15: O. Eulenstein, "Predictions of Gene-Duplications and Their Phylogenetic Development," PhD dissertation, Univ. of Bonn, Germany. gMD Research Series No. 20/1998, ISSN: 1435-2699, 1998.
• 16: L. Zhang, "On a Mirkin-Muchnik-Smith Conjecture for Comparing Molecular Phylogenies," J. Computational Biology, vol. 4, no. 2, pp. 177-187, 1997.
• 17: K. Chen, D. Durand, and M. Farach-Colton, "NOTUNG: A Program for Dating Gene Duplications and Optimizing Gene Family Trees," J. Computational Biology, vol. 7, no. 3/4, 2000.
• 18: Paola Bonizzoni , Gianluca Della Vedova , Riccardo Dondi, Reconciling a gene tree to a species tree under the duplication cost model, Theoretical Computer Science, v.347 n.1-2, p.36-53, 30 November 2005 [doi>10.1016/j.tcs.2005.05.016]
• 19: P. Górecki and J. Tiuryn, "On the Structure of Reconciliations," Proc. Second RECOMB Comparative Genomics Satellite Workshop, J. Lagergren, ed., pp. 42-54, 2004.
• 20: Michael A. Bender , Martin Farach-Colton, The LCA Problem Revisited, Proceedings of the 4th Latin American Symposium on Theoretical Informatics, p.88-94, April 10-14, 2000
• 21: Dov Harel , Robert Endre Tarjan, Fast algorithms for finding nearest common ancestors, SIAM Journal on Computing, v.13 n.2, p.338-355, May 1984 [doi>10.1137/0213024]
• 22: Michael R. Fellows , Michael T. Hallett , Chantal Korostensky , Ulrike Stege, Analogs and Duals of teh MAST Problem for Sequences and Trees, Proceedings of the 6th Annual European Symposium on Algorithms, p.103-114, August 24-26, 1998
• 23: Ulrike Stege, Gene Trees and Species Trees: The Gene-Duplication Problem in Fixed-Parameter Tractable, Proceedings of the 6th International Workshop on Algorithms and Data Structures, p.288-293, August 11-14, 1999
• 24: M. T. Hallett , J. Lagergren, New algorithms for the duplication-loss model, Proceedings of the fourth annual international conference on Computational molecular biology, p.138-146, April 2000, Tokyo, Japan [doi>10.1145/332306.332359]
• 25: M. Bordewich and C. Semple, "On the Computational Complexity of the Rooted Subtree Prune and Regraft Distance," Annals of Combinatorics, vol. 8, pp. 409-423, 2004.
• 26: M.S. Bansal, J.G. Burleigh, O. Eulenstein, and A. Wehe, "Heuristics for the Gene-Duplication Problem: A ¿(n) Speed-Up for the Local Search," Proc. 11th Ann. Int'l Conf. Research in Computational Molecular Biology (RECOMB '07), T.P. Speed and H. Huang, eds., pp. 238-252, 2007.
• 27: Mark de Berg , Marc van Kreveld , Mark Overmars , Otfried Schwarzkopf, Computational geometry: algorithms and applications, Springer-Verlag New York, Inc., Secaucus, NJ, 1997

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

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

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation; Pattern analysis

General Terms:
Algorithms, Design, Theory

Keywords:
Algorithms, Phylogenetics, Computational Biology, Gene Duplication, Supertrees