Average complexity of the Jiang-Wang-Zhang pairwise tree alignment algorithm and of a RNA secondary structure alignment algorithm

被引：6

作者：

Herrbach, Claire ^{[1
,2
]}

Denise, Alain ^{[1
,2
]}

Dulucq, Serge ^{[3
]}

机构：

[1] Univ Paris 11, LRI, CNRS, F-91405 Orsay, France

[2] Univ Paris 11, IGM, CNRS, F-91405 Orsay, France

[3] Univ Bordeaux 1, LaBRI, CNRS, F-33405 Talence, France

来源：

THEORETICAL COMPUTER SCIENCE | 2010年 / 411卷 / 26-28期

关键词：

Average complexity; Tree alignment; RNA alignment; RNA structure; EDIT; DISTANCE;

D O I：

10.1016/j.tcs.2010.01.014

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that the average complexity of the pairwise ordered tree alignment algorithm of Jiang, Wang and Zhang is in O(nm), where n and in stand for the sizes of the two trees, respectively. We show that the same result holds for the average complexity of pairwise comparison of RNA secondary structures, using a set of biologically relevant operations. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：2423 / 2432

页数：10

共 14 条

[1]

[Anonymous], 1994, FDN COMPUTER SCI

[2]

BLIN G, 2010, IEEE ACM T IN PRESS

[3]

BLIN G, 2006, 13 INT S STRING PROC, V4209

[4]

BLIN G, 2007, INT S COMB ALG PROB, V4614

[5] PATTERNS IN TREES [J].

DERSHOWITZ, N ;

ZAKS, S .

DISCRETE APPLIED MATHEMATICS, 1989, 25 (03) :241-255

[6] RNA secondary structure comparison: exact analysis of the Zhang-Shasha tree edit algorithm [J].

Dulucq, S ;

Tichit, L .

THEORETICAL COMPUTER SCIENCE, 2003, 306 (1-3) :471-484

[7]

DULUCQ S, 2003, P 14 ANN S COMB PATT

[8]

HERRBACH C, 2006, 1451 LRI

[9] ALIGNMENT OF TREES - AN ALTERNATIVE TO TREE EDIT [J].

JIANG, T ;

WANG, LS ;

ZHANG, KZ .

THEORETICAL COMPUTER SCIENCE, 1995, 143 (01) :137-148

[10] A general edit distance between RNA structures [J].

Jiang, T ;

Lin, GH ;

Ma, B ;

Zhang, KZ .

JOURNAL OF COMPUTATIONAL BIOLOGY, 2002, 9 (02) :371-388

← 1 2 →