cDNAマッピングのためのマッチング連鎖アルゴリズム

スポンサーリンク

概要

• 論文の詳細を見る

• 論文では、新しいcDNAマッピングを効率的かつ正確に行えるアルゴリズムを提案する。このアルゴリズムでは、接尾辞木などを利用して得ることができるMUM (maximal unique match)あるいはMRM (maximal rare match)と呼ばれる配列間のマッチング(共通文字列)の集合の中から最適な部分集合を選ぶ、というマッチング連鎖問題というものを解くことによって、cDNAマッピングを行う。このマッチング連鎖問題に対しては、マッチングの数をkとすると、マッテング間の重なりを考慮しない場合であれば、O(k log k)時間のアルゴリズムが知られているが、重なりを考慮した場合にはO(k^2)時間のアルゴリズムしか知られていなかった。本論文では、これに対し、O(k log k)時間のアルゴリズムを提案する。更に、このアルゴリズムをマウスにおける実際のcDNAマッピングの問題に適用し、専門家によるマッピングと比較した場合、95%以上の精度と97%以上の再現率が得られることを示した。

• 2003-09-18

著者

• KUROCHKIN Igor

  理化学研究所ゲノム情報科学研究グループ

• 渋谷 哲朗

  日本アイ・ビー・エム(株)東京基礎研究所

• Kurochkin Igor

  理化学研究所ゲノム科学総合研究センター

関連論文

• cDNAマッピングのためのマッチング連鎖アルゴリズム
• スプライスト・アライソメントに基づいたcDNAライブラリの正確なクラスタリング・アルゴリズム
• モチーフ検索アルゴリズムと遺伝子同定への応用
• アルファベットサイズの大きな木のSuffix Treeについて
• 生物学的配列の組換えの解析のための新しいアプローチ
• 電子マネーシステムにおける最適なオンラインアルゴリズム
• A^*アルゴリズムを用いたn×m最短路問題の効率的解法
• 構文情報に基づく情報抽出システム開発のためのツール(ツール,質問応答,要約)

スポンサーリンク