Alignments of RNA Structures

被引：27

作者：

Blin, Guillaume ^{[1
]}

Denise, Alain ^{[2
,3
]}

Dulucq, Serge ^{[4
]}

Herrbach, Claire ^{[2
,3
]}

Touzet, Helene ^{[5
,6
]}

机构：

[1] Univ Paris Est, CNRS, UMR 8049, Inst Gaspard Monge, F-77454 Marne La Vallee 2, France

[2] Univ Paris 11, Rech Informat Lab, CNRS, UMR 8623, F-91405 Orsay, France

[3] Univ Paris 11, Inst Genet & Microbiol, CNRS, UMR 8621, F-91405 Orsay, France

[4] Univ Bordeaux 1, CNRS, UMR 5800, Lab Bordelais Rech Informat, F-33405 Talence, France

[5] Univ Lille 1, CNRS, UMR 8022, Lab Informat Fondamentale Lille, F-59650 Villeneuve Dascq, France

[6] INRIA Lille Nord Europe, F-59650 Villeneuve Dascq, France

来源：

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS | 2010年 / 7卷 / 02期

关键词：

Computational biology; RNA structures; arc-annotated sequences; NP-hardness; edit distance; algorithm; COMPUTING SIMILARITY; SECONDARY STRUCTURES; EDIT DISTANCE; ALGORITHMS; SEQUENCES; TREES;

D O I：

10.1109/TCBB.2008.28

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

We describe a theoretical unifying framework to express the comparison of RNA structures, which we call alignment hierarchy. This framework relies on the definition of common supersequences for arc-annotated sequences and encompasses the main existing models for RNA structure comparison based on trees and arc-annotated sequences with a variety of edit operations. It also gives rise to edit models that have not been studied yet. We provide a thorough analysis of the alignment hierarchy, including a new polynomial-time algorithm and an NP-completeness proof. The polynomial-time algorithm involves biologically relevant edit operations such as pairing or unpairing nucleotides. It has been implemented in a software, called gardenia, which is available at the Web server http://bioinfo.lifl.fr/RNA/gardenia.

引用

页码：309 / 322

页数：14

共 29 条

[1]

ALLALI J, 2004, P IWABI 2004 BERG NO, P412

[2]

[Anonymous], 2004, J DISCRETE ALGORITHM, DOI DOI 10.1016/S1570-8667(03)00080-7

[3]

Bafna V, 1995, LECT NOTES COMPUT SC, V937, P1

[4] BOOK THICKNESS OF A GRAPH [J].

BERNHART, F ;

KAINEN, PC .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (03) :320-331

[5] On triangulating planar graphs under the four-connectivity constraint [J].

Biedl, T ;

Kant, G ;

Kaufmann, M .

ALGORITHMICA, 1997, 19 (04) :427-446

[6]

BLIN G, 2007, P 1 INT S COMB ALG P, P140

[7]

BLIN G, 2006, P 13 INT S STRING PR, P291

[8] The Ribonuclease P Database [J].

Brown, JW .

NUCLEIC ACIDS RESEARCH, 1999, 27 (01) :314-314

[9] The Comparative RNA Web (CRW) Site:: an online database of comparative sequence and structure information for ribosomal, intron, and other RNAs -: art. no. 2 [J].

Cannone, JJ ;

Subramanian, S ;

Schnare, MN ;

Collett, JR ;

D'Souza, LM ;

Du, YS ;

Feng, B ;

Lin, N ;

Madabusi, LV ;

Müller, KM ;

Pande, N ;

Shang, ZD ;

Yu, N ;

Gutell, RR .

BMC BIOINFORMATICS, 2002, 3 (1)

[10]

CROCHEMORE M, 2005, P 13 ANN EUR S ALG E, P426

← 1 2 3 →