Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots

Mathias Möhl; Sebastian Will; Rolf Backofen

doi:10.1007/978-3-540-69068-9_9

Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots

Mathias Möhl
, Sebastian Will
, Rolf Backofen

Universität des Saarlandes
University of Freiburg

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We present an algorithm for computing the edit distance of two RNA structures with arbitrary kinds of pseudoknots. A main benefit of the algorithm is that, despite the problem is NP-hard, the algorithmic complexity adapts to the complexity of the RNA structures. Due to fixed parameter tractability, we can guarantee polynomial run-time for a parameter which is small in practice. Our algorithm can be considered as a generalization of the algorithm of Jiang et al. [1] to arbitrary pseudoknots. In their absence, it gracefully degrades to the same polynomial algorithm. A prototypical implementation demonstrates the applicability of the method.

Original language	English
Title of host publication	Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings
Pages	69-81
Number of pages	13
DOIs	https://doi.org/10.1007/978-3-540-69068-9_9
Publication status	Published - 1 Jul 2008
Externally published	Yes
Event	19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 - Pisa, Italy Duration: 18 Jun 2008 → 20 Jun 2008

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	5029 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008
Country/Territory	Italy
City	Pisa
Period	18/06/08 → 20/06/08

Keywords

Fixed parameter tractability
Pseudoknots
RNA alignment

Access to Document

10.1007/978-3-540-69068-9_9

Cite this

Möhl, M., Will, S., & Backofen, R. (2008). Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots. In Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings (pp. 69-81). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5029 LNCS). https://doi.org/10.1007/978-3-540-69068-9_9

Möhl, Mathias ; Will, Sebastian ; Backofen, Rolf. / Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots. Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings. 2008. pp. 69-81 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{2b857f69b4b4419d814b306fb87a1ce7,

title = "Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots",

abstract = "We present an algorithm for computing the edit distance of two RNA structures with arbitrary kinds of pseudoknots. A main benefit of the algorithm is that, despite the problem is NP-hard, the algorithmic complexity adapts to the complexity of the RNA structures. Due to fixed parameter tractability, we can guarantee polynomial run-time for a parameter which is small in practice. Our algorithm can be considered as a generalization of the algorithm of Jiang et al. [1] to arbitrary pseudoknots. In their absence, it gracefully degrades to the same polynomial algorithm. A prototypical implementation demonstrates the applicability of the method.",

keywords = "Fixed parameter tractability, Pseudoknots, RNA alignment",

author = "Mathias M{\"o}hl and Sebastian Will and Rolf Backofen",

year = "2008",

month = jul,

day = "1",

doi = "10.1007/978-3-540-69068-9\_9",

language = "English",

isbn = "3540690662",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "69--81",

booktitle = "Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings",

note = "19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008 ; Conference date: 18-06-2008 Through 20-06-2008",

}

Möhl, M, Will, S & Backofen, R 2008, Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots. in Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 5029 LNCS, pp. 69-81, 19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008, Pisa, Italy, 18/06/08. https://doi.org/10.1007/978-3-540-69068-9_9

Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots. / Möhl, Mathias; Will, Sebastian; Backofen, Rolf.
Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings. 2008. p. 69-81 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5029 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots

AU - Möhl, Mathias

AU - Will, Sebastian

AU - Backofen, Rolf

PY - 2008/7/1

Y1 - 2008/7/1

N2 - We present an algorithm for computing the edit distance of two RNA structures with arbitrary kinds of pseudoknots. A main benefit of the algorithm is that, despite the problem is NP-hard, the algorithmic complexity adapts to the complexity of the RNA structures. Due to fixed parameter tractability, we can guarantee polynomial run-time for a parameter which is small in practice. Our algorithm can be considered as a generalization of the algorithm of Jiang et al. [1] to arbitrary pseudoknots. In their absence, it gracefully degrades to the same polynomial algorithm. A prototypical implementation demonstrates the applicability of the method.

AB - We present an algorithm for computing the edit distance of two RNA structures with arbitrary kinds of pseudoknots. A main benefit of the algorithm is that, despite the problem is NP-hard, the algorithmic complexity adapts to the complexity of the RNA structures. Due to fixed parameter tractability, we can guarantee polynomial run-time for a parameter which is small in practice. Our algorithm can be considered as a generalization of the algorithm of Jiang et al. [1] to arbitrary pseudoknots. In their absence, it gracefully degrades to the same polynomial algorithm. A prototypical implementation demonstrates the applicability of the method.

KW - Fixed parameter tractability

KW - Pseudoknots

KW - RNA alignment

UR - https://www.scopus.com/pages/publications/45849125023

U2 - 10.1007/978-3-540-69068-9_9

DO - 10.1007/978-3-540-69068-9_9

M3 - Conference contribution

AN - SCOPUS:45849125023

SN - 3540690662

SN - 9783540690665

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 69

EP - 81

BT - Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings

T2 - 19th Annual Symposium on Combinatorial Pattern Matching, CPM 2008

Y2 - 18 June 2008 through 20 June 2008

ER -

Möhl M, Will S, Backofen R. Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots. In Combinatorial Pattern Matching - 19th Annual Symposium, CPM 2008, Proceedings. 2008. p. 69-81. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-540-69068-9_9

Fixed parameter tractable alignment of RNA structures including arbitrary pseudoknots

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this