本論文では、大量の短配列データに対して、参照ゲノム配列と比較照合して類似する部分配列の位置を特定する「ゲノム・マッピング問題」を、高速かつ高精度に解くために新たに開発した幾つかの基本アルゴリズムについて述べる。対象とする短配列データは、長さ30~100塩基程度の数百万本以上のDNA塩基配列データであり、対象とする参照ゲノム配列は、ヒトなどの高等生物の数十億塩基対にも及ぶ大型のゲノム塩基配列である。

このようなゲノム・マッピング問題は、2000年代後半に「次世代型DNAシーケンサ」と称される超並列型DNAシーケンサが登場したことを背景として、そこから得られる大量のDNA配列データを解析して生物学的に有用な情報を得るための最初の重要なステップの一つとして、近年注目されるようになってきた。

第1章のイントロダクションでは、このような問題背景について手短に紹介し、コンピュータ・サイエンスの分野で関連する幾つかの技術について言及したのち、以後の各章で取り上げる話題の位置付けを述べる。

第2章では、Burrows-Wheeler変換を用いて高速なゲノム・マッピングを行う際に基礎となる、ランク関数とセレクト関数の新しい高速計算法を提案した。これらの関数は、指定された部分文字列内に含まれるAやCなどの特定の文字の出現回数をカウントする関数である。ゲノム・マッピング問題は、Burrows-Wheeler変換されたゲノム配列上でランク関数やセレクト関数を計算する問題に帰着させることができ、それにより効率的に解くことができる。これらの関数の計算に適したデータ構造とし階層的バイナリ文字列(Hierarchical Binary String)を提案した。これは、バイナリ文字列に対して、その先頭から各文字位置までの部分和のビット表示を8ビットを1桁として分解し、各桁を上位桁に上がるごとに256分の1に間引きその差分ビットを並べた列を上位桁のバイナリ文字列として、階層構造を与えたものである。この構造化に伴うメモリ量のオーバヘッドの割合は、文字列長に依存せず常に約3.5%と少ない。長さnのバイナリ文字列には、hをlog 2 n / 8以上の最小の整数として、h階層の構造が与えられる。上記の関数は階層数hに比例した時間で高速に計算でき、例えば64ギガビットのランダム文字列の場合であれば、8ギガバイト強のメモリと3ギガヘルツのCPUで1マイクロ秒未満で計算できる。これらを従来から知られている他の方法と比較すると、メモリ量のオーバヘッドの割合は約20分の1に抑えられ、計算速度は少なくとも同等以上になると評価された。また、これらをマッピング問題に応用して評価した。長さ24~41塩基の短配列データに対して、クエリー配列当たり高々1個以下の不一致(置換、挿入、または、欠失)を許す条件を課して、上記CPUで毎秒2,000~4,800本程度をマッピングできた。これは、短配列用の最も高速なマッピング・ツールの一つであるELANDより3~7倍程度高速であった。

第3章では、ペアエンド配列のゲノム・マッピング問題を扱う。次世代型DNAシーケンサでは、配列長が比較的短く、マッピング位置を特定するための情報が不足しがちである。そこで、この短所を補うため、ペアエンド方式とよばれるシーケンシング法が用いられる。この方式では、長さを調整された配列断片の両端の末端配列をペアとしてシーケンシングする。従って、ペアエンド配列のゲノム・マッピング問題では、ペアをなす配列を、互いにほぼ一定距離だけ離れた位置にマッピングすることが求められる。即ち、この場合、単に文字列照合するだけでなく、位置の制約を考慮する必要がある。最も素朴な解法は、最初に各配列を独立にゲノム・マッピングした後で、位置制約を満たすものを選ぶという方法である。この方法では、ペアエンド配列がリピート領域に由来する場合、最初に膨大なヒットを生じて、処理効率の低下を招きやすい。一方、サフィックス・アレイやBurrows-Wheeler変換などの従来の方法では、辞書式順にデータをソートすることにより、文字列照合は効率的に行えるが、そのとき同時に位置の制約を考慮することは困難であった。そこで、文字列照合と位置制約考慮を同時に効率的に行える新しいデータ構造として、局所化サフィックス・アレイ(Localized Suffix Array)を提案した。局所化サフィックス・アレイは、大まかな位置情報を表わす上位ビットと、そこで局所的にソートされた辞書式順序情報を表わす下位ビットから構成され、これら2種類の情報が混在した情報を扱えるという特徴をもち、実装上は、通常のサフィックス・アレイの内部のビットを入れ替えたものとして実現できる。局所化サフィックス・アレイを用いることにより、リピート領域に由来する配列の場合は、多数のマッピング候補位置を徐々に詳細化しながら、制約を満たさない候補位置は一括して排除することが可能となる。これらの計算はランク関数の計算に帰着され、第2章で提案したアルゴリズムを用いて高速に計算される。それにより候補位置が2,000箇所以上ある場合に平均10倍以上の高速化の効果が得られることを、36塩基長のペアエンド配列の実データを用いて確認した。

第4章では、2塩基符号化(Two-Base Encoding)方式で得られたシーケンシング・エラー率が比較的高い配列データに対するゲノム・マッピング問題を扱う。2塩基符号化方式では隣り合った2塩基の4×4通りの組み合わせを4色の蛍光で検出するため、一次配列データとしては4色からなるカラー配列が得られ、それを塩基配列に復号化する。この方式のメリットの一つは、カラー配列と参照ゲノム配列のアラインメントが得られれば、符号化の冗長性を利用してシーケンシング・エラーを訂正することができ、最終的に高品質の配列データが得られる点にある。そのためには、多数のエラーを含んだ状態で、カラー配列と参照ゲノム配列とのアラインメントを求める必要がある。即ち、多数の不一致を許容するゲノム・マッピングを求める問題を解く必要がある。このような問題、或いは、一般に高感度なホモロジー・サーチに適した方法として、穴開きシード(spaced seeds)を利用する方法が従来から知られている。しかしながら、高感度化のためには複数のマスクパターン(穴開きのパターン)を利用する必要が生じてインデクス・データの肥大化を招きやすい。また、穴開きシードをBurrows-Wheeler変換で効率的に扱うことは難しく、それらのインデクス・データを大幅に圧縮することは望めない。そこで、穴開きシードを用いずに、通常の連続シードのみを用いて、Burrows-Wheeler変換によるコンパクトなインデクス・データとメモリ容量で、高速・高感度にゲノム・マッピングを行う方法を検討した。但し、高頻度の不一致に対応するためには、シード内部にも若干の不一致を許容する必要があり、また、比較的短いシードを利用する必要がある。このようなシードは計算コストの上昇を招きやすいため、高感度で効率的なシードのセットを構築するための新たな方法を提案した。シードの役割は、広範囲なゲノム全体の中から候補位置を絞り込むこと、即ち、候補位置の情報を知らせることにある。その情報量は、逆に、候補位置がどの程度曖昧か、即ち、候補位置がどれだけ残っているかによって捉えることができる。例えば、リピート領域に由来するシードは、多数の候補位置を提示し、その情報量は少ないと考えられる。また、一般に、マッピング処理全体の計算コストは、全てのシードに対する候補位置の数の総和に概ね比例する。従って、候補位置の数はシードの特性を表わす重要な指標である。また、その対数をとったものは、情報理論の観点からは候補位置の曖昧性を測るエントロピーとも解釈できる。そこで、エントロピーの観点から高感度で効率的なシードのセットを求める方法として、等エントロピー分割法(Equi-Entropy Partitioning, EEP)を提案した。この方法では、クエリー配列を同程度のエントロピーをもつ断片配列に分割し、それらの断片配列を組合わせて各シードを構成する。それにより、例えば、リピート領域では長めのシードが採用され、逆に一意性が高い領域では短めのシードが採用され、高精度と高速性を両立させることが可能になる。HLA(Human Leukocyte Antigen)領域をシーケンシングした一千万本の50塩基長のシングル・エンド配列の実データを用いて評価を行い、穴開きシードを利用した短配列用の高感度なゲノム・マッピング・ツールであるBFASTと比較して、ほぼ同程度の精度を達成でき、約1.3倍高速になるという結果を得た。そのとき、ヒトゲノムのインデクス・データのサイズは約30分の1(約4ギガ・バイト)に、必要なメモリ量は約4分の1(約4ギガ・バイト)に抑えられた。

最後の第5章では結言を述べる。

以上のように、本論文では、次世代型DNAシーケンサから得られる大量の短配列データから生物学的知見を得るために有用な情報を提供するゲノム・マッピング処理を、高速・高精度に行うための幾つかの基本アルゴリズムを提案し、その有効性を実データを用いて確認した。

本論文は、近年その驚異的な進歩によって生命科学に大きなインパクトを与えている次世代型DNAシークエンサーから産出された塩基配列断片が、ゲノム中で対応する位置を高速で検索する「塩基配列マッピング問題」に関する研究結果をまとめたものである。理想的には断片配列と一致する部分配列がゲノム上のどこかに存在するはずであるから、高速な部分文字列マッチングアルゴリズムを適用すれば済むはずであるが、実際には断片配列は無視できないほど高い実験エラーを含み、参照されるゲノム配列も断片配列をうみだしたゲノムと同一ではないので、文字間の不一致などを考慮する必要があるし、断片配列が転写産物からとられた場合は、イントロンの存在も無視できない。このような事情を考慮したアルゴリズムは、従来でもBLASTを始めとして、数多く開発されてきたものの、次世代シークエンサーの生み出すデータは、その量が桁違いに多く、実験エラー率の高さや断片長の短さをも考慮にいれて最適化したアルゴリズムを開発する必要がある。すなわち、計算速度と記憶容量の両面での最適化が望まれる。実際ここ数年、この分野は非常に活況を呈しており、次々と新しいアルゴリズムやツールが発表されているが、我が国からの貢献は少ないという状況下で、論文申請者の以下に述べる貢献は、世界的に先駆的なものを含む、貴重なものであると言える。

論文の主な内容は、第一章の序論に続く、3つの章に分かれている。

第二章では、ゲノム塩基配列への高速マッピングに適した手法として、近年サフィックス・アレイなどの従来法に代わって注目されているBurrows-Wheeler変換に基づくマッピング用の効率的なデータ構造として、階層的バイナリ文字列を提案している。一般にゲノムのマッピング問題はBurrows-Wheeler変換されたゲノム配列上でランク関数やセレクト関数を計算する問題に帰着させることができるが、このデータ構造を用いれば、これらの関数を比較的少ないメモリ使用量で高速に計算できる。その性能は計算機実験でも確認している。

第三章では、ペアエンド方式の配列データを効率的に扱うためのデータ構造として、局所化サフィックス・アレイを提案している。ペアエンド法は、次世代型シークエンサー等から得られた配列がしばしばユニークにマッピングできない状況、特にゲノムがリピート配列を多く含んでいる場合の困難、を克服するためによく用いられる方法で、ほぼ一定の長さの塩基配列の両端の配列を決定する。このため、二つの読み取られた配列(リード)は、ある距離の範囲にマップされなければならないという制約条件がつくが、この条件をサフィックス・アレイや、Burrows-Wheeler変換などにおいて、効率的に取り扱うことは困難であった。申請者らが提案したデータ構造を用いれば、この問題をうまく解決でき、そのことは実データを用いた計算機実験でも実証している。

第四章では、マップされる配列のエラー率が高く、ゲノム配列とのミスマッチが多い場合に適したマッピングアルゴリズムを提唱している。このような状況は、たとえばライフテクノロジー社のSOLiDシークエンサーのデータを扱うときに問題になる。SOLiDでは、隣接2塩基の配列を4色で表現する2塩基符号化法を用いているため、データの復号化の過程でエラーを訂正できるものの、元データのリード配列のエラー率は比較的高くなってしまう。一方、BLASTをはじめとする、ミスマッチを含む配列のアラインメントを高速に求めるアルゴリズムの基本戦略は、まず調べたい配列の短い部分配列(シード配列)がターゲット配列中に完全一致する場所を高速に検出し、その後、その周囲をじっくり調べることである。検索配列が短くてエラーを多く含んでいる場合、このシード配列をどう設定するかが問題になる。その解決策として、シードの中にマッチを調べない場所を設ける穴開きシードを用いる方法が広く用いられているが、メモリ使用量が多くなるという欠点をもつ。そこで申請者は、本章で等エントロピー分割法という方法を用いて、シード配列を柔軟に求めることを提唱している。この方法の原理は、検索配列からシードをとるときに、ターゲット配列中に候補位置が何個ぐらいかが大体同じになるように、その長さを調節するというものである。申請者は、この方法を、穴開きシードを用いたBFASTプログラムと実データを用いて比較したところ、速度と感度を犠牲にせずに、大幅なメモリの節約を実現できることを確認した。

以上、記してきたように、本論文に記された申請者の研究内容は、いずれも生命科学の最新の課題の解決に向けた、オリジナルな貢献を示すものであり、学術的に評価できる。従って、博士(生命科学)の学位を授与できると認める。