Seeded Tree Alignment
- 13 June 2008
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 5 (4) , 503-513
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.Keywords
This publication has 26 references indexed in Scilit:
- Local Gapped Subforest Alignment and Its Application in Finding RNA Structural MotifsJournal of Computational Biology, 2006
- A novel algorithm and web-based tool for comparing two alternative phylogenetic treesBioinformatics, 2005
- Constrained tree inclusionJournal of Discrete Algorithms, 2005
- Tree pattern matching in phylogenetic trees: automatic search for orthologs or paralogs in homologous gene sequence databasesBioinformatics, 2005
- Faster Subtree IsomorphismJournal of Algorithms, 1999
- Comparing multiple RNA secondary structures using tree comparisonsBioinformatics, 1990
- Tree graphs of RNA secondary structures and their comparisonsComputers and Biomedical Research, 1989
- The secondary structure of ribonuclease P RNA, the catalytic element of a ribonucleoprotein enzymeCell, 1988
- O(n2.5) time algorithms for the subgraph homeomorphism problem on treesJournal of Algorithms, 1987
- An Analysis of a Good Algorithm for the Subtree ProblemSIAM Journal on Computing, 1977