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.
論文 | ランダム
- エキシマランプを用いたフォトエッチングの基礎特性
- 直流回生車の方式と諸特性
- 広島県極楽寺山のアカマツ衰退林における針葉含水率とアブシジン酸(ABA)濃度の季節変化
- Complex Environmental Factors Affecting the Decline of Pinus densiflora in the Seto Inland Sea Area of Western Japan
- 高強度薄板鋼板の製造におけるベイナイト変態の利用