情報処理学会 第87回全国大会

5ZL-02
遺伝子配列アライメントに対する量子アニーリングの応用
○赤松辰哉,牧野浩典(東海大)
 DNAやタンパク質の配列解析は,生物間の進化的・系統的な関係の特定やタンパク質の機能・構造の予測をする重要なプロセスである.解析するにあたり2本の配列を比較する基本的な手法としてペアワイズアライメントがある.これは2本のアミノ酸配列に対して適切な位置にギャップを挿入し,各配列中の同じ位置に重要なアミノ酸が並ぶように操作をすることで,各配列の類似度を評価する手法である.しかし、大規模配列ではギャップ挿入位置の最適化がNP困難となり、既存のアルゴリズムでは効率的な解の取得が困難である。我々はこの組合せ最適化問題に対して,量子アニーリングを用いたペアワイズアライメントの最適解を導出する手法を提案する.