The Gene-Duplication Problem: Near-Linear Time Algorithms for NNI-Based Local Searches

ABSTRACT

The gene-duplication problem is to infer a species supertree from a collection of gene trees that are confounded by complex histories of gene-duplication events. This problem is NP-complete 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. A classical local search problem is the {\tt NNI} search problem, which is based on the nearest neighbor interchange operation. In this work, we 1) provide a novel near-linear time algorithm for the {\tt NNI} search problem, 2) introduce extensions that significantly enlarge the search space of the {\tt NNI} search problem, and 3) present algorithms for these extended versions that are asymptotically just as efficient as our algorithm for the {\tt NNI} search problem. The exceptional speedup achieved in the extended {\tt NNI} search problems makes the gene-duplication problem more tractable for large-scale phylogenetic analyses. We verify the performance of our algorithms in a comparison study using sets of large randomly generated gene trees.

REFERENCES

• 1: M.S. Bansal and O. Eulenstein, "The Gene-Duplication Problem: Near-Linear Time Algorithms for NNI-Based Local Searches," Proc. Int'l Symp. Bioinformatics Research and Applications (ISBRA), pp. 14-25, May 2008.
• 2: 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.
• 3: 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.
• 4: Ilan Wapinski , Avi Pfeffer , Nir Friedman , Aviv Regev, Automatic genome-wide reconstruction of phylogenetic gene trees, Bioinformatics, v.23 n.13, p.i549-i558, July 2007 [doi>10.1093/bioinformatics/btm193]
• 5: I. Wapinski, A. Pfeffer, N. Friedman, and A. Regev, "Natural History and Evolutionary Principles of Gene Duplication in Fungi," Nature, vol. 449, pp. 54-61, 2007.
• 6: L. Arvestad, A.-C. Berglund, J. Lagergren, and B. Sennblad, "Bayesian Gene/Species Tree Reconciliation and Orthology Analysis Using MCMC," Proc. Int'l Conf. Intelligent Systems for Molecular Biology (ISMB) (Supplement of Bioinformatics), pp. 7-15, 2003.
• 7: Lars Arvestad , Ann-Charlotte Berglund , Jens Lagergren , Bengt Sennblad, Gene tree reconstruction and orthology analysis based on an integrated model for duplications and sequence evolution, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.326-335, March 27-31, 2004, San Diego, California, USA [doi>10.1145/974614.974657]
• 8: Bin Ma , Ming Li , Louxin Zhang, From Gene Trees to Species Trees, SIAM Journal on Computing, v.30 n.3, p.729-752, 2000 [doi>10.1137/S0097539798343362]
• 9: R.D.M. Page, "GeneTree: Comparing Gene and Species Phylogenies Using Reconciled Trees," Bioinformatics, vol. 14, no. 9, pp. 819- 820, 1998.
• 10: J. Felsenstein, Inferring Phylogenies, pp. 37-46. Sinauer Assoc., 2004.
• 11: C. Semple and M. Steel, Phylogenetics, pp. 30-33. Oxford Univ. Press, 2003.
• 12: 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.
• 13: 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.
• 14: R.D.M. Page and M.A. Charleston, "From Gene to Organismal Phylogeny: Reconciled Trees and the Gene Tree/Species Tree Problem," Molecular Phylogenetics and Evolution, vol. 7, pp. 231- 240, 1997.
• 15: 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.
• 16: D. Chen, O. Eulenstein, D. Fernández-Baca, and J.G. Burleigh, "Improved Heuristics for Minimum-Flip Supertree Construction," Evolutionary Bioinformatics, vol. 2, pp. 347-356, 2006.
• 17: M.S. Bansal, J.G. Burleigh, O. Eulenstein, and A. Wehe, "Heuristics for the Gene-Duplication Problem: A ¿(n) Speedup for the Local Search," Proc. Ann. Int'l Conf. Research in Computational Molecular Biology (RECOMB), pp. 238-252, 2007.
• 18: Mukul S. Bansal , Oliver Eulenstein, An Ω(n^2/ log n) Speed-Up of TBR Heuristics for the Gene-Duplication Problem, IEEE/ACM Transactions on Computational Biology and Bioinformatics (TCBB), v.5 n.4, p.514-524, October 2008 [doi>10.1109/TCBB.2008.69]
• 19: G. Ganapathy, V. Ramachandran, and T. Warnow, "Better Hill-Climbing Searches for Parsimony," Proc. Workshop Algorithms in Bioinformatics (WABI), pp. 245-258, 2003.
• 20: Ganeshkumar Ganapathy , Vijaya Ramachandran , Tandy Warnow, On contract-and-refine transformations between phylogenetic trees, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 21: 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.
• 22: 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.
• 23: O. Eulenstein, "Predictions of Gene-Duplications and Their Phylogenetic Development," PhD dissertation, Univ. of Bonn, GMD Research Series no. 20/1998, 1998.
• 24: L. Zhang, "On a Mirkin-Muchnik-Smith Conjecture for Comparing Molecular Phylogenies," J. Computational Biology, vol. 4, no. 2, pp. 177-187, 1997.
• 25: 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, pp. 429-447, 2000.
• 26: 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]
• 27: P. Górecki and J. Tiuryn, "On the Structure of Reconciliations," Proc. Research in Computational Molecular Biology (RECOMB) Comparative Genomics Workshop, pp. 42-52, Oct. 2004.
• 28: 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
• 29: 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, pp. 349- 362, 1997.
• 30: R.D.M. Page, "Extracting Species Trees from Complex Gene Trees: Reconciled Trees and Vertebrate Phylogeny," Molecular Phylogenetics and Evolution, vol. 14, pp. 89-106, 2000.
• 31: R.D.M. Page and J. Cotton, "Vertebrate Phylogenomics: Reconciled Trees and Gene Duplications," Proc. Pacific Symp. Biocomputing , pp. 536-547, 2002.
• 32: 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, pp. 107-125, Springer-Verlag, 2004.
• 33: M.J. Sanderson and M.M. McMahon, "Inferring Angiosperm Phylogeny from EST Data with Widespread Gene Duplication," BMC Evolutionary Biology, vol. 7, (Suppl. 1): S3, 2007.
• 34: 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
• 35: 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
• 36: 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]
• 37: B. DasGupta , X. He , T. Jiang , M. Li , J. Tromp , L. Zhang, On distances between phylogenetic trees, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.427-436, January 05-07, 1997, New Orleans, Louisiana, United States
• 38: André Wehe , Mukul S. Bansal , J. Gordon Burleigh , Oliver Eulenstein, DupTree, Bioinformatics, v.24 n.13, p.1540-1541, July 2008 [doi>10.1093/bioinformatics/btn230]

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
          Subjects: Sorting and searching

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
  I.6 SIMULATION AND MODELING
      I.6.4 Model Validation and Analysis

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
Computational phylogenetics, gene-duplication, supertrees, local search, {\tt NNI}.