Seeded Tree Alignment

ABSTRACT

The optimal transformation of one tree into another by means of elementary edit operations is an important algorithmic problem that has several interesting applications to computational biology. Here we introduce a constrained form of this problem in which a partial mapping of a set of nodes (the "seeds") in one tree to a corresponding set of nodes in the other tree is given, and present efficient algorithms for both ordered and unordered trees. Whereas ordered tree matching based on seeded nodes has applications in pattern matching of RNA structures, unordered tree matching based on seeded nodes has applications in co-speciation and phylogeny reconciliation. The latter involves the solution of the planar tanglegram layout problem, for which a polynomial-time algorithm is given here.

REFERENCES

• 1: Moon Jung Chung, O(n^2.5) time algorithms for the subgraph homeomorphism problem on trees, Journal of Algorithms, v.8 n.1, p.106-112, March 1987 [doi>10.1016/0196-6774(87)90030-7]
• 2: 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
• 3: Jean-François Dufayard , Laurent Duret , Simon Penel , Manolo Gouy , François Rechenmann , Guy Perrière, Tree pattern matching in phylogenetic trees: automatic search for orthologs or paralogs in homologous gene sequence databases, Bioinformatics, v.21 n.11, p.2596-2603, June 2005 [doi>10.1093/bioinformatics/bti325]
• 4: J. Felsenstein, "Phylip--Phylogeny Inference Package (Version 3.2)," Cladistics, vol. 5, no. 1, pp. 164-166, 1989.
• 5: Ulrich Fößmeier , Michael Kaufmann, Nice Drawings for Planar Bipartite Graphs, Proceedings of the Third Italian Conference on Algorithms and Complexity, p.122-134, March 12-14, 1997
• 6: J.A. Gallian, "A Dynamic Survey of Graph Labeling," Electronic J. Combinatorics, no. DS7, http://www.combinatorics.org/Surveys/, 2007.
• 7: K.J. Gardiner, T.L. Marsh, and N.R. Pace, "Ion Dependence of the Bacillus Subtilis RNase P Reaction," J. Biological Chemistry, vol. 260, no. 9, pp. 5415-5419, 1985.
• 8: E.S. Haas and J.W. Brown, "Evolutionary Variation in Bacterial RNase P RNAs," Nucleic Acids Research, vol. 26, no. 18, pp. 4093-4099, 1998.
• 9: J.K. Harris, E.S. Haas, D. Williams, D.N. Frank, and J.W. Brown, "New Insight into RNase P RNA Structure from Comparative Analysis of the Archaeal RNA," RNA, vol. 7, no. 2, pp. 220-232, 2001.
• 10: P. Hugenholtz, "Exploring Prokaryotic Diversity in the Genomic Era," Genome Biology, vol. 3, no. 2, pp. reviews0003.1- reviews0003.8, 2002.
• 11: B.D. James, G.J. Olsen, J. Liu, and N.R. Pace, "The Secondary Structure of Ribonuclease P RNA, the Catalytic Element of a Ribonucleoprotein Enzyme," Cell, vol. 52, no. 1, pp. 19-26, 1988.
• 12: J. Jansson, N.T. Hieu, and W.-K. Sung, "Local Gapped Subforest Alignment and Its Application in Finding RNA Structural Motifs," J. Computational Biology, vol. 13, no. 3, pp. 702-718, 2006.
• 13: S.-Y. Le , R. Nussinov , J. V. Maizel, Tree graphs of RNA secondary structures and their comparisons, Computers and Biomedical Research, v.22 n.5, p.461-473, Oct. 1989 [doi>10.1016/0010-4809(89)90039-6]
• 14: A. Lozano, R. Pinter, O. Rokhlenko, G. Valiente, and M. Ziv-Ukelson, "Seeded Tree Alignment and Planar Tanglegram Layout," Proc. Seventh Workshop Algorithms in Bioinformatics (WABI '07), vol. 4645, pp. 98-110, 2007.
• 15: B.L. Maidak, J.R. Cole, T.G. Lilburn, C.T. Parker, P.R. Saxman, J.M. Stredwick, G.M. Garrity, B. Li, G.J. Olsen, S. Pramanik, T.M. Schmidt, and J.M. Tiedje, "The RDP (Ribosomal Database Project) Continues," Nucleic Acids Research, vol. 28, pp. 173-174, 2000.
• 16: D.W. Matula, "An Algorithm for Subtree Identification," SIAM Rev., vol. 10, pp. 273-274, 1968.
• 17: D. Matula, "Subtree Isomorphism in O(n^5/2)," Annals Discrete Math., vol. 2, pp. 91-106, 1978.
• 18: Tom M.W. Nye , Pietro Liò , Walter R. Gilks, A novel algorithm and web-based tool for comparing two alternative phylogenetic trees, Bioinformatics, v.22 n.1, p.117-119, January 2006 [doi>10.1093/bioinformatics/bti720]
• 19: N.R. Pace and J.W. Brown, "Evolutionary Perspective on the Structure and Function of Ribonuclease P, A Ribozyme," J. Bacteriology, vol. 177, no. 8, pp. 1919-1928, 1995.
• 20: R.D.M. Page, ed., Tangled Trees: Phylogeny, Cospeciation, and Coevolution. The Univ. of Chicago Press, 2002.
• 21: R.D.M. Page and G. Valiente, "An Edit Script for Taxonomic Classifications," BMC Bioinformatics, vol. 6, p. 208, 2005.
• 22: R.Y. Pinter, O. Rokhlenko, D. Tsur, and M. Ziv-Ukelson, "Approximate Labelled Subtree Homeomorphism," Proc. 15th Ann. Symp. Combinatorial Pattern Matching (CPM '04), vol. 3109, pp. 59-73, 2004.
• 23: S.W. Reyner, "An Analysis of a Good Algorithm for the Subtree Problem," SIAM J. Computing, vol. 6, no. 4, pp. 730-732, 1977.
• 24: Ron Shamir , Dekel Tsur, Faster Subtree Isomorphism, Journal of Algorithms, v.33 n.2, p.267-280, Nov. 1999 [doi>10.1006/jagm.1999.1044]
• 25: Huiyuan Shan , Katherine G. Herbert , William H. Piel , Dennis Shasha , Jason Tsong-Li Wang, A Structure-Based Search Engine for Phylogenetic Databases, Proceedings of the 14th International Conference on Scientific and Statistical Database Management, p.7-10, July 24-26, 2002 [doi>10.1109/SSDM.2002.1029699]
• 26: B.A. Shapiro and K. Zhang, "Comparing Multiple RNA Secondary Structures Using Tree Comparisons," Computer Applications in the Biosciences, vol. 6, no. 4, pp. 309-318, 1990.
• 27: Dennis Shasha , Jason T. L. Wang , Rosalba Giugno, Algorithmics and applications of tree and graph searching, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543620]
• 28: Gabriel Valiente, Algorithms on Trees and Graphs, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 29: G. Valiente, "Constrained Tree Inclusion," J. Discrete Algorithms, vol. 3, nos. 2-4, pp. 431-447, 2005.
• 30: G. Valiente, "A Fast Algorithmic Technique for Comparing Large Phylogenetic Trees," Proc. 12th Int'l Symp. String Processing and Information Retrieval (SPIRE '05), vol. 3772, pp. 371-376, 2005.
• 31: C.R. Woese and N.R. Pace, "Probing RNA Structure, Function, and History by Comparative Analysis," The RNA World, R.F. Gesteland and J.F. Atkins, eds., pp. 91-117, Cold Spring Harbor Laboratory Press, 1993.
• 32: Wan Nazmee Wan Zainon , Paul Calder, Visualising phylogenetic trees, Proceedings of the 7th Australasian User interface conference, p.145-152, January 16-19, 2006, Hobart, Australia
• 33: Kaizhong Zhang , Lusheng Wang , Bin Ma, Computing Similarity between RNA Structures, Proceedings of the 10th Annual Symposium on Combinatorial Pattern Matching, p.281-293, July 22-24, 1999

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: Pattern matching

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees; Graph algorithms

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology

General Terms:
Algorithms, Design, Theory

Keywords:
Graph algorithms, Graph Theory, Discrete Mathematics, Mathematics of Computing, Trees, Biology and genetics, Life and Medical Sciences, Computer Applications