IEICE TRANSACTIONS on Fundamentals
Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences
Summary :
It is well known that a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem can be solved in O(n3) time by using simple dynamic programming procedures. For this problem, an O(n3(log log n)1/2/(log n)1/2) time exact algorithm and an O(n2.776+(1/ε)O(1)) time approximation algorithm which has guaranteed approximation ratio 1-ε for any positive constant ε are also known. Moreover, when two RNA sequences are given, there is an O(n6) time exact algorithm which can optimize structure and alignments. In this paper, we show an O(n5) time approximation algorithm for optimizing structure and alignments of two RNA sequences with assuming that the optimal number of base-pairs is more than O(n0.75). We also show that the problem to optimize structure and alignments for given N sequences is NP-hard and introduce a constant-factor approximation algorithm.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E90-A No.5 pp.917-923
- Publication Date
- 2007/05/01
- Publicized
- Online ISSN
- 1745-1337
- DOI
- 10.1093/ietfec/e90-a.5.917
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Cite this
Copy
Takeyuki TAMURA, Tatsuya AKUTSU, "Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences" in IEICE TRANSACTIONS on Fundamentals,
vol. E90-A, no. 5, pp. 917-923, May 2007, doi: 10.1093/ietfec/e90-a.5.917.
Abstract: It is well known that a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem can be solved in O(n3) time by using simple dynamic programming procedures. For this problem, an O(n3(log log n)1/2/(log n)1/2) time exact algorithm and an O(n2.776+(1/ε)O(1)) time approximation algorithm which has guaranteed approximation ratio 1-ε for any positive constant ε are also known. Moreover, when two RNA sequences are given, there is an O(n6) time exact algorithm which can optimize structure and alignments. In this paper, we show an O(n5) time approximation algorithm for optimizing structure and alignments of two RNA sequences with assuming that the optimal number of base-pairs is more than O(n0.75). We also show that the problem to optimize structure and alignments for given N sequences is NP-hard and introduce a constant-factor approximation algorithm.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1093/ietfec/e90-a.5.917/_p
Copy
@ARTICLE{e90-a_5_917,
author={Takeyuki TAMURA, Tatsuya AKUTSU, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences},
year={2007},
volume={E90-A},
number={5},
pages={917-923},
abstract={It is well known that a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem can be solved in O(n3) time by using simple dynamic programming procedures. For this problem, an O(n3(log log n)1/2/(log n)1/2) time exact algorithm and an O(n2.776+(1/ε)O(1)) time approximation algorithm which has guaranteed approximation ratio 1-ε for any positive constant ε are also known. Moreover, when two RNA sequences are given, there is an O(n6) time exact algorithm which can optimize structure and alignments. In this paper, we show an O(n5) time approximation algorithm for optimizing structure and alignments of two RNA sequences with assuming that the optimal number of base-pairs is more than O(n0.75). We also show that the problem to optimize structure and alignments for given N sequences is NP-hard and introduce a constant-factor approximation algorithm.},
keywords={},
doi={10.1093/ietfec/e90-a.5.917},
ISSN={1745-1337},
month={May},}
Copy
TY - JOUR
TI - Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 917
EP - 923
AU - Takeyuki TAMURA
AU - Tatsuya AKUTSU
PY - 2007
DO - 10.1093/ietfec/e90-a.5.917
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E90-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2007
AB - It is well known that a basic version (i.e., maximizing the number of base-pairs) of the RNA secondary structure prediction problem can be solved in O(n3) time by using simple dynamic programming procedures. For this problem, an O(n3(log log n)1/2/(log n)1/2) time exact algorithm and an O(n2.776+(1/ε)O(1)) time approximation algorithm which has guaranteed approximation ratio 1-ε for any positive constant ε are also known. Moreover, when two RNA sequences are given, there is an O(n6) time exact algorithm which can optimize structure and alignments. In this paper, we show an O(n5) time approximation algorithm for optimizing structure and alignments of two RNA sequences with assuming that the optimal number of base-pairs is more than O(n0.75). We also show that the problem to optimize structure and alignments for given N sequences is NP-hard and introduce a constant-factor approximation algorithm.
ER -
English
