Seeded Tree Alignment

被引：9

作者：

Lozano, Antoni ^{[1
]}

Pinter, Ron Y. ^{[2
]}

Rokhlenko, Oleg ^{[3
]}

Valiente, Gabriel ^{[4
]}

Ziv-Ukelson, Michal ^{[5
]}

机构：

[1] Tech Univ Catalonia, Dept Software, Log & Programming Res Grp, E-08034 Barcelona, Spain

[2] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

[3] IBM Res Lab, IL-31905 Haifa, Israel

[4] Tech Univ Catalonia, Dept Software, Algorithms Bioinformat Complex & Formal Methods R, E-08034 Barcelona, Spain

[5] Ben Gurion Univ Negev, Dept Comp Sci, IL-84105 Beer Sheva, Israel

来源：

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS | 2008年 / 5卷 / 04期

关键词：

RNA structure alignment; comparative phylogenetics; tree matching; tanglegram layout;

D O I：

10.1109/TCBB.2008.59

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

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 cospeciation and phylogeny reconciliation. The latter involves the solution of the planar tanglegram layout problem, for which a polynomial-time algorithm is given here.

引用

页码：503 / 513

页数：11

共 33 条

[1]

[Anonymous], RNA WORLD

[2]

[Anonymous], 2002, ALGORITHMS TREES GRA

[3]

[Anonymous], 2002, Tangled Trees: Phylogeny, Cospeciation, and Coevolution

[4]

[Anonymous], 1989, Cladistics, DOI DOI 10.1111/J.1096-0031.1989.TB00562.X

[5] O(N2.5) TIME ALGORITHMS FOR THE SUBGRAPH HOMEOMORPHISM PROBLEM ON TREES [J].

CHUNG, MJ .

JOURNAL OF ALGORITHMS, 1987, 8 (01) :106-112

[6] Tree pattern matching in phylogenetic trees:: automatic search for orthologs or paralogs in homologous gene sequence databases [J].

Dufayard, JF ;

Duret, L ;

Penel, S ;

Gouy, M ;

Rechenmann, F ;

Perrière, G .

BIOINFORMATICS, 2005, 21 (11) :2596-2603

[7]

Fossmeier U, 1997, LECT NOTES COMPUT SC, V1203, P122

[8]

GALLIAN JA, 2007, ELECT J COMBINATORIC

[9]

GARDINER KJ, 1985, J BIOL CHEM, V260, P5415

[10] Evolutionary variation in bacterial RNase P RNAs [J].

Haas, ES ;

Brown, JW .

NUCLEIC ACIDS RESEARCH, 1998, 26 (18) :4093-4099

← 1 2 3 4 →