Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences(<Special Section>Discrete Mathematics and Its Applications)
スポンサーリンク
概要
- 論文の詳細を見る
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(n^3) time by using simple dynamic programming procedures. For this problem, an O(n^3(loglogn)^<1/2>/(logn)^<1/2>) time exact algorithm and an O(n^<2.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(n^6) time exact algorithm which can optimize structure and alignments. In this paper, we show an O(n^5) 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(n^<0.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.
- 社団法人電子情報通信学会の論文
- 2007-05-01
著者
-
Akutsu Tatsuya
Kyoto Univ. Kyoto‐shi Jpn
-
Akutsu Tatsuya
Bioinformatics Center, Institute for Chemical Research, Kyoto University
-
TAMURA Takeyuki
Bioinformatics Center, Institute for Chemical Research, Kyoto University
-
Akutsu Tatsuya
Bioinformatics Center Institute For Chemical Research Kyoto University
-
Tamura Takeyuki
Bioinformatics Center Institute For Chemical Research Kyoto University
-
Akutsu Tatsuya
Bioinformatics Center Inst. For Chemical Res. Kyoto Univ.
関連論文
- Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
- Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
- On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
- Approximation Algorithms for Optimal RNA Secondary Structures Common to Multiple Sequences(Discrete Mathematics and Its Applications)
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Dynamic Programming and Clique Based Approaches for Protein Threading with Profiles and Constraints(Discrete Mathematics and Its Applications)
- Inferring pedigree graphs from genetic distances
- Hardness Results on Local Multiple Alignment of Biological Sequences
- 1P-279 酸化ストレス下におけるアポトーシス制御機構の数理的解明(放射線生物/活性酸素,第46回日本生物物理学会年会)
- Detecting a Singleton Attractor in a Boolean Network Utilizing SAT Algorithms
- Exact Algorithms for Finding a Minimum Reaction Cut under a Boolean Model of Metabolic Networks
- On Finding a Fixed Point in a Boolean Network with Maximum Indegree 2
- Tree Edit Distance Problems: Algorithms and Applications to Bioinformatics
- Message from the Editor-in-Chief
- Message from the Editor-in-Chief
- Analyses and Algorithms for Predecessor and Control Problems for Boolean Networks of Bounded Indegree
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- A Clustering Method for Analysis of Sequence Similarity Networks of Proteins Using Maximal Components of Graphs
- Message from the Editor-in-Chief
- Message from the Editor-in-Chief
- Hardness Results on Local Multiple Alignment of Biological Sequences
- Kernel Methods for Chemical Compounds: From Classification to Design
- Conservation Laws and Symmetries in Competitive Systems
- Measuring the Similarity of Protein Structures Using Image Compression Algorithms
- An Efficient Method of Computing Impact Degrees for Multiple Reactions in Metabolic Networks with Cycles
- Conservation Laws and Symmetries in Competitive Systems
- Integer Programming-Based Approach to Attractor Detection and Control of Boolean Networks
- On the Complexity of Inference and Completion of Boolean Networks from Given Singleton Attractors