Introduction

Molecular cloning is an established and reliable way to isolate and to sequence specific fragments of DNA sequences. We can mention important applications of cloning such as the construction of full-length cDNA libraries and fosmid clone end-sequencing for whole genome sequencing and structural variation discovery. With the increase of throughput provided by second-generation sequencing technologies recently, application of these technologies in clone sequencing approaches can be considered to reduce the cost and the time consumed when traditional capillary sequencing is employed. However, computational problems arise mainly because of the short length of reads and the parallel property of the method. Here, I propose and develop computational approaches to tackle these limitations in the assembly of full-length cDNA clones and in the pooling of non-overlapping clones for high-throughput sequencing.

Methods

The replacement of capillary sequencers with Illumina GA is a cost-efficient extension to the existing approach of multiclone-shotgun sequencing of cDNA clones. As the high accuracy of the sequence that is required in these projects is fundamental to provide reliable information about the complete coding sequences, I propose a new de novo-reference hybrid assembly approach that generates sequences to fulfill that quality requirement. This new method, MuSICA 2, assembles full-length cDNA sequences of hundreds of clones from several short reads sequenced by Illumina GA, requiring Sanger reads from either or both ends of the clones to identify individual clone sequences in the assembly.

The assembly strategy used was a hybrid of reference assembly and de novo assembly, taking advantage of the benefits of both different approaches. Initial contigs are generated by de novo assembly of short reads that are generally fragmented because of the conservative aspect of this approach. Aligning disjoint contigs with the reference genome generates many overlapping alignments. Because we assume that clone sequences are non-overlapping on the genome, then we can confidently merge overlapping contigs with the help of the reference genome. These alignments are also used to identify exon sequences as well as sequences across exon-intron junctions that might be missing in the assembly. Alignments of short reads with exon filling candidate regions and spliced-alignments of short reads with intron filling candidate regions were used to close gaps in the assembly. The final contigs are finally identified and associated with individual clones by using Sanger reads from clone ends.

In our assembly approach, I assume that simultaneously sequenced clones do not overlap on the genome. As clone end-sequences are often obtained before sequencing the full insert of clones, such as in cDNA clone sequencing and in genomic structural variation detection with fosmid libraries, then we can use their location information to define an optimization problem to select non-overlapping clones for high-throughput sequencing. The objective is to arrange clones that overlap on the genome in different pools, minimizing the number of sequencing runs. Overlaps on the genome are defined with an interval graph G = (V, E), in which two overlapping clones (v1,v2)∈E are assigned to different pools. If E=〓, the specific problem corresponds to the classical bin-packing problem, or if the sequence sizes are ignored, then it is equivalent to the graph coloring problem. The non-overlapping clone pooling problem is a generalization of both specific problems and therefore is also computationally intractable. To provide near-optimal solutions for this problem, approximation algorithms based on bin-packing heuristics and optimal coloring are proposed and discussed.

Results

To evaluate the accuracy of the assembly of full-length cDNA sequences, I compared the output of our approach for human and toxoplasma cDNA clones with sequences finished by the traditional Sanger method. The assembly steps were successful in increasing the sequence contiguity. The exon-intron structure of the coding sequence was correct for more than 95% of the clones with coding sequence annotation and the nucleotide-level accuracy of coding sequences of those clones was over 99.99%. These results show that high sequence quality can be achieved for the sequencing of full-length cDNA clones using Illumina GA, reducing the cost and time by one order of magnitude when compared with traditional Sanger method.

To assess the performance of the approximation algorithms proposed for the non-overlapping clone pooling problem, real data from full-length cDNA clones and simulated end sequences from real fosmid clones were used. Optimal solutions could be found by a combination of optimal coloring and bin-packing heuristics, showing the applicability of the approach with real data.

本論文は4章からなる。第1章はイントロダクション、第2章はクローン化された cDNA を数百本混ぜて DNA断片をシーケンスし、ゲノムへと写像することにより cDNAを低コストで配列決定する方法について述べている。第3章はcDNA, fosmid 等のクローンの両端配列があらかじめ分かっているときに、その両端配列をゲノム上に写像することでクローン同士が重なるかどうかを判定し、重ならないクローンを別々のグループに分けてシーケンスする方法を展開している。最後に第4章は研究の結論を述べている。

第1章では、研究の動機、cDNAクローンの配列を決定するアプローチの概要、その問題点を述べている。従来はサンガー法に基づくシーケンサーにより高精度の配列を解読してきたが、コストが高額であることが問題であった。そのため低コストで大量の塩基を解読することが出来る次世代型シーケンサーにより、低コストで高精度の配列決定化できるかどうかを考察している。このように研究の動機は明確である。

第2章では、クローン化されたcDNAを約800本混ぜ合わせたプールを、次世代シーケンサー技術を使って解読し、混合した配列を参照するゲノム配列へアラインメントすることにより、cDNAの exon-intron 構造を復元するアプローチを詳細に検討している。本問題を検討した2008年ごろには、解読配列長が36塩基と短かったため、短いexon の同定が難しかった。また繰り返し配列などにより断片配列をゲノム上で唯一の位置へと写像することも困難であった。さらに intron をはさんで exon を繋げることは容易ではなかった。このような様々な困難な問題を乗り越えて、cDNA配列を復元できるようにしたことは重要である。しかし、現在では75-100塩基程度の長さが標準的に読めるようになったため、技術的な苦労は少なくなっている。現在のシーケンス技術水準のもとでは、提案方法の価値は薄まりつつある。その点についても考察している。またソフトウエアは公開しており、シーケンス速度が指数関数的増加にている現在の状況に対応するための努力を継続している。コストは毎年さがるため最新の価格での比較は難しい。しかし過去の水準で比較はしており、現在でも参考的資料としての価値は高い。

第3章では、論文の後半では、ゲノム上で重なり合わないように様々なクローンを混ぜてプールをつくり、次世代シーケンサーにより解読することを考察している。シーケンスの回数を減らし、コストを抑えるために、プールの数が少なくなるような近似的なアルゴリズムを利用している。既存のアルゴリズムを使用しており、理論的に優れたアルゴリズムを提案しているわけではないものの、実用的価値は高く普及する可能性がある。

第4章では、上記の研究から導かれる結論について述べられている。まとめるとcDNAクローンを次世代型シーケンサーで解読することにより、高い精度を維持しながら、大幅なコストダウンを実現できることを示している。

なお、本論文は、森下真一、笠原雅弘、鈴木穣、菅野純夫との共同研究であるが、論文提出者が主体となって開発、分析及び検証を行ったもので、論文提出者の寄与が十分であると判断する。

したがって、博士(科学)の学位を授与できると認める。