Dynamic Programming and Clique Based Approaches for Protein Threading with Profiles and Constraints(<Special Section>Discrete Mathematics and Its Applications)

スポンサーリンク

概要

• 論文の詳細を見る

• The protein threading problem with profiles is known to be efficiently solvable using dynamic programming. In this paper, we consider a variant of the protein threading problem with profiles in which constraints on distances between residues are given. We prove that protein threading with profiles and constraints is NP-hard. Moreover, we show a strong hardness result on the approximation of an optimal threading satisfying all the constraints. On the other hand, we develop two practical algorithms: CLIQUETHREAD and BBDPTHREAD. CLIQUETHREAD reduces the threading problem to the maximum edge-weight clique problem, whereas BBDPTHREAD combines dynamic programming and branch-and-bound techniques. We perform computational experiments using protein structure data in PDB (Protein Data Bank) using simulated distance constraints. The results show that constraints are useful to improve the alignment accuracy of the target sequence and the template structure. Moreover, these results also show that BBDPTHREAD is in general faster than CLIQUETHREAD for larger size proteins whereas CLIQUETHREAD is useful if there does not exist a feasible threading.

• 社団法人電子情報通信学会の論文
• 2006-05-01

著者

• Hayashida Morihiro

  Bioinformatics Center Institute For Chemical Research Kyoto University

• Akutsu Tatsuya

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• Tomita Etsuji

  Univ. Electro‐communications Chofu‐shi Jpn

• Suzuki Jun'ichi

  Graduate School Of Electro-communications The University Of Electro-communications

• Tomita Etsuji

  Univ. Electro‐communications Tokyo Jpn

• BAHADUR K.

  Bioinformatics Center, Institute for Chemical Research, Kyoto University

• TOMITA Etsuji

  Graduate School of Electro-communications, The University of Electro-Communications

• HORIMOTO Katsuhisa

  Human Genome Center, Institute of Medical Science, The University of Tokyo

• Tomita Etsuji

  Graduate School Of Electro-communications The University Of Electro-communications

• Akutsu Tatsuya

  Bioinformatics Center Institute For Chemical Research Kyoto University

• Horimoto Katsuhisa

  Human Genome Center Institute Of Medical Science The University Of Tokyo

• Bahadur K.

  Bioinformatics Center Institute For Chemical Research Kyoto University

• Hayashida Morihiro

  Bioinformatics Center Inst. For Chemical Res. Kyoto Univ.

• 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
• The maximum clique problem and its applications (数理モデル化と問題解決 バイオ情報学)
• 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)
• 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

もっと見る 閉じる

スポンサーリンク