Recent discoveries have been shown that DNA molecules became one of the most fundamental information in genetic sciences. Knowledge of DNA sequences will be ultimately fruitful for curing complicated diseases as the case of cancers for example. Decoding the code of life (i.e. DNA) into human natural languages will eventually lead us to new findings in various fields including medicine, biology, forensic biology, biochemistry, biotechnology and agriculture.

To obtain the genome sequence of any species needed what is now called sequencing technology. The complexity of DNA molecule structure as well as its tininess prevents any current sequencing technology to sequence the whole genome at once. As a result, we could not obtain the complete genome sequence but a set of reads that include sequencing errors and sometimes contaminated with cloning vectors or other foreign genomes. Bringing these reads all together in order to reconstruct the original genome sequence is called the (whole) genome assembly problem in literature. The different challenges that came along with DNA reads pushed computer scientists to design and develop more sophisticated assembly algorithms. This research topic epitomizes the backbone of this thesis. As a result, we developed an automated and systematic genome assembly system that was divided into two important sets of tools: preprocessing tools and assembly tools.

Because of the hugeness of sequencing data and the difficulty of other different constraints, we aimed at designing different tools for preparing the data to be independent from any genome assembler. Consequently, we could universalize the input of our assemblers to be "theoretically" adapted for any sequencing technology. By this way, the output data can be used for other purposes as well, and whenever a new sequencing technology appears in the market, we can just create simple tool for converting its data to the universalized input of our assemblers. More so, we can concentrate on developing the assembly algorithms regardless of the characteristics of the data produced by any sequencing technology. This separation can lead us to build more robust assemblers and creating new tools for preparing, analyzing, visualizing and validating the sequencing data. During this research, we could develop a sequencing errors corrector, trimming tool and other useful as well. In the first part of this thesis, we will explain in details the design and algorithms of each of these tools.

Most of genome assembly approaches use graph theory algorithms and data structures. Two approaches have been used to design the assemblers: the overlap graph-based approach and the de Bruijn graph-based approach. Each approach has some weak and good points. Creating more efficient assemblers requires analyzing the chosen graph more deeply so that it can be safely traversed for constructing long contiguous sequences. We discovered new substructures in the de Bruijn graph with the aim of developing a genome assembler that is able to produce more accurate results and avoid the misassemblies as much as possible. Assembly algorithms were kept simple, fast and designed in a cascaded way. As a result, we could develop two specialized de novo assemblers: Arapan-S and Arapan-M. We will explain step-by-step the overall architecture of our assemblers as well as the algorithms used in their different stages.

We will express and show the performance of each tool we created in the result section of each chapter throughout this thesis.

本論文は、生物のDNA配列の断片データ(DNAシークエンスデータ)から、ゲノム配列を再構築するゲノムアセンブリ問題の解決を試みている。現在の計測技術では一度に計測できるDNA断片長が全ゲノムに比して極端に短いことから、複雑な構造を有する生物種のゲノム配列の決定には様々な困難が存在する。そのためゲノムアセンブリ問題は、データの前処理を含む多種の部分問題からなり、最終的に精度を向上させるためには、それぞれの問題に対して深い洞察を基に適切に対処し、システム全体を構築する必要がある。本論文では、シークエンスデータの前処理と、アセンブリを行う後処理とを明確に分け、それぞれの問題に対してアプローチを考えることで計測技術の差異に過度に依存しない、汎用的かつ精度の高いアセンブリシステムの開発を試みている。計測データ前処理に対しては、シークエンスデータに含まれる計測エラーおよびクローニングベクターとよばれる他種の生物由来の配列を、それぞれ検出および除去する新規アルゴリズム群を考案し、既存手法を上回る精度を示している。後処理であるアセンブリにおいては、シークエンスデータを基に構成されるグラフ構造から、配列情報の曖昧性を表現する部分構造の解消に主に着目し、解消段階において考慮すべき新規部分構造群を提案し、それぞれの解消アルゴリズムを考案している。またグラフ構造からDNA配列を推定する段階においても、従前使われてきたグラフ理論的に依拠した手法ではなく、より計測データの信頼性に依拠した新規アルゴリズムを考案し、システム全体として既存手法と比して高い精度でゲノムアセンブリを行うことに成功している。

本論文は七章からなり、第一章では、ゲノムアセンブリ問題の背景および動機を明らかにし、上記問題に対する提案手法群の貢献の概要を述べている。第二章では、ゲノムアセンブリ問題を解くための元データである、DNAシークエンスデータを産生する技術のサーベイを行っている。また既存のゲノムアセンブリ手法が、Overlap graphに依拠するものと、de Bruijn graphに依拠するものとの二種に大別されることを述べ、それぞれの特徴を説明し、本研究でde Bruijn graphに基づく戦略を採用した動機を述べている。第三章では、提案手法に基づき実装したシステムの構成を述べている。システム全体は、シークエンスの生データの前処理を行うものと、処理後のシークエンスデータを入力としてアセンブルを行うアセンブラからなることを示し、それぞれの役割と開発の指針を説明している。第四章では、シークエンス生データの前処理を行うために提案した手法群(DNA ScissorおよびQamar)のアルゴリズムの説明および性能評価を行っている。DNA Scissorはシークエンスデータに混入するクローニングベクター由来の配列の除去を行う手法であり、Qamarはシークエンスデータに含まれる配列読み取りエラーの訂正アルゴリズムである。提案手法を様々なシミュレーションデータおよび実データセットに対して適用し、各提案手法がそれぞれの既存手法よりも精度が高いことを明らかにしている。第五章では、提案した二種のアセンブラー(Arapan-SおよびArapan-M)のアルゴリズムを説明し、それぞれのアセンブラーを種々の実データに対して適用し既存手法と性能を比較し提案手法の有効性を明らかにしている。Arapan-Sは小規模ゲノム用のアセンブラーであり、de Bruijn graph中のバブルと呼ばれる部分グラフ構造の解消に高速なアルゴリズムを提案している。またアセンブリアルゴリズムとして、従前使われてきたグラフ中の最短経路を探索する方法ではなく、グラフ中のノードに付随するk-mer配列の頻度または長さの情報を利用する新規手法も提案し、双方の性能を比較し結果を議論している。一方、Arapan-Mは、Arapan-Sを基に開発された長い繰り返し配列を含む中規模ゲノム用のアセンブラーであり、申請者はde Bruijn graphの注意深い観察から、グラフ構造のクリーニングの段階において解消されるべきものとして四種の新規部分グラフ構造を見いだし、それぞれの解消アルゴリズムを提案している。更に各部分グラフ構造のアセンブル精度への寄与を実データに対する実験により示し結果を議論している。第六章では、本研究を進めるに当たり開発した種々のツール群のアルゴリズムを説明し、性能を評価している。第七章では、研究の概括と今後の展望を述べている。

本論文は、ゲノムアセンブリにおいて直面する多種多様な問題に対して現実的かつ効果的な解決策を与えるものであり、今後の研究への指針を示すという点で大きな貢献をなすものであり評価に値する。

よって本論文は博士(情報理工学)の学位請求論文として合格と認められる。