Paper Info
Title
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.
Year
DOI
Venue
2008
10.1109/TCBB.2008.59
Computational Biology and Bioinformatics, IEEE/ACM Transactions
Keywords
Field
DocType
interesting application,corresponding set,life and medical sciences,seeded tree alignment,discrete mathematics,trees,optimal transformation,partial mapping,unordered tree,mathematics of computing,biology and genetics,phylogeny reconciliation,graph algorithms,planar tanglegram layout problem,computer applications,polynomial-time algorithm,rna structure,graph theory,important algorithmic problem,pattern matching,rna,genetics,macromolecules,phylogeny,polynomials,molecular biophysics,microorganisms,algorithm design and analysis,binary trees,computational biology,bioinformatics
Range tree,Computer science,K-ary tree,Tree (data structure),Algorithm,Binary tree,Theoretical computer science,Tree structure,Bioinformatics,Segment tree,Tree alignment,Interval tree
Journal
Volume
Issue
ISSN
5
4
1557-9964
Citations 
PageRank 
References 
8
0.58
19
Authors
5
Name
Order
Citations
PageRank
Antoni Lozano113511.96
Ron Pinter247852.83
Oleg Rokhlenko325017.03
Gabriel Valiente474263.30
Michal Ziv-Ukelson551436.49