塩基配列用の高速パタ-ン照合アルゴリズムの研究

点击翻译按钮获取中文摘要

文字列パタ-ン照合とは,文字列パタ-ンのテキスト中における出現位置を検出することであり,これまでにも情報検索システムやデ-タベ-スシステムにおいて最も基本的かつ重要な機構として活用されてきている.遺伝情報の本体であるDNAは,基本的には,‘A',‘T','C',‘G'の4種類の記号からなる文字列である.本研究の目的は,パタ-ン照合の処理対象がDNAの塩基配列である場合を取り上げて,その高速なアルゴリズムの実現方法について研究を進めていくとともに,実際にゲノム研究者のツ-ルとして有用なシステムの構築を行うことである.本年度は,次の2点を中心に研究を進めた。1.塩基配列用パタ-ン照合アルゴリズムの高速化さまざまな観点から塩基配列用のパタ-ン照合アルゴリズムについて考察し,その高速化の可能性を探る.とくに,情報圧縮を利用する高速化や並列化による高速化について塩基配列への適用可能性を検討する。DNA塩基配列デ-タを構成する文字種は非常に少なく,しかもそのほとんどが,‘A',‘T',‘C',‘G'であるが,通常のシステムでは,これをそのまま計算機の文字(8ビット)で表現している.このデ-タをHuffman符号によって圧縮し,それをそのまま復号することなく走査するアルゴリズムを考案した.これにより,デ-タを効率的に圧縮し,しかも検索を高速に実行することが可能であることがわかった.2.テキストデ-タベ-ス管理システムSIGMAの整備SIGMAは,著者らが開発し,九州大学大型計算機センタ-で一般に公開している汎用のテキストデ-タベ-ス管理システムであり,高速な文字列パタ-ン照合アルゴリズムを駆使した効果的な情報システムである。このSIGMAシステムをゲノム研究者のツ-ルとして活用できるように整備していく。DNA塩基配列デ-タベ-スGanBankをSIGMAのファイルに変換し,管理・検索できることを確認した。これを,全国の研究者が共同利用できるデ-タベ-スとして公開すれば,ゲノム研究者によるさまざまな検索が可能になる.