Hardness Results on Local Multiple Alignment of Biological Sequences
スポンサーリンク
概要
- 論文の詳細を見る
This paper studies the local multiple alignment problem, which is, given protein or DNA sequences, to locate a region (i.e., a substring) of fixed length from each sequence so that the score determined from the set of regions is optimized. We consider the following scoring schemes: the relative entropy score (i.e., average information content), the sum-of-pairs score and a relative entropy-like score introduced by Li, et al. We prove that multiple local alignment is NP-hard under each of these scoring schemes. In particular, we prove that multiple local alignment is APX-hard under relative entropy scoring. It implies that unless P =NP there is no polynomial time algorithm whose worst case approximation error can be arbitrarily specified(precisely, a polynomial time approximation scheme). Several related theoretical results are also provided.
著者
-
Arimura Hiroki
Graduate School Of Information Science And Technology Hokkaido University
-
Shimozono Shinichi
Department Of Artificial Intelligence Kyushu Institute Of Technology
-
Akutsu Tatsuya
Bioinformatics Center Inst. For Chemical Res. Kyoto Univ.
関連論文
- Prediction of Protein Folding Rates from Structural Topology and Complex Network Properties
- 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)
- Knowledge Acquisition from Amino Sequences by Machine Learning System BONSAI
- Hardness Results on Local Multiple Alignment of Biological Sequences
- 1P-279 酸化ストレス下におけるアポトーシス制御機構の数理的解明(放射線生物/活性酸素,第46回日本生物物理学会年会)
- Frequent closed item set mining based on zero-suppressed BDDs (論文特集:データマイニングと統計数理)
- Complexity of Finding Alphabet Indexing
- 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
- A Dynamically Reconfigurable FPGA-Based Pattern Matching Hardware for Subclasses of Regular Expressions
- An Efficient Method of Computing Impact Degrees for Multiple Reactions in Metabolic Networks with Cycles
- Conservation Laws and Symmetries in Competitive Systems
- A Dynamically Reconfigurable FPGA-Based Pattern Matching Hardware for Subclasses of Regular Expressions
- 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