配列のローカル・アラインメントの困難さについて
スポンサーリンク
概要
- 論文の詳細を見る
複数の文字列が与えられた時、類似性やエントロピーが最大となるように各文字列から同じ長さの部分文字列を切り出してくる問題はギャップ無しのローカル・マルチプル・アラインメントと呼ばれ、似た機能を持つDNA配列やアミノ酸配列から特徴的な部分を取り出してくるのに有用である。この問題に対し、EMアルゴリズムやギッブスサンプリングなどに基づくヒューリスティックなアルゴリズムや分枝限定法によるアルゴリズムが提案されてきたが、最適解を計算する多項式時間アルゴリズムは開発されていなかった。本稿では、エントロピーおよびSP (Sum of Pairs) スコアのいずれのスコアを用いても、この問題がNP困難であることを示す。
- 一般社団法人情報処理学会の論文
- 1999-05-14
著者
-
阿久津 達也
東京大学 医科学研究所 ヒトゲノム解析センター
-
阿久津 達也
京都大学化学研究所バイオインフォマティクスセンター:京都大学大学院情報学研究科知能情報学専攻
-
阿久津 達也
東京大学医科学研究所ヒトゲノム解析センター
関連論文
- 代謝ネットワークの最小反応カットを求めるアルゴリズム
- 整数計画法を用いたブーリアンネットワークの解析・制御手法(システムバイオロジー,システムバイオロジー,一般)
- 高さの制限された無順序木の編集距離問題に対する近似アルゴリズム
- タンパク質ドメインネットワークに対する二部グラフのモデル
- タンパク質間相互作用ネットワークにおける相互作用ドメイン対の確率的選択に基づくべき乗分布のモデル化
- 分子生物情報学の現状と動向 (「分子生物情報学の新展開」)
- 特集「分子生物情報学の新展開の編集にあたって (「分子生物情報学の新展開」)
- 最適degenerate pattern探索アルゴリズムと転写因子結合部位同定問題への適用
- 最適 degenerate pattern 探索アルゴリズムと転写因子結合部位同定問題への適用
- 高さの制限された2個の無順序木に対する最大共通部分木の近似アルゴリズムの改良