EXACT ALGORITHMS FOR GENOME ASSEMBLY

Abstract

In my thesis work, I explored the possibility and feasibility of solving problems of scaffolding and finishing genomes using exact algorithms. First, I explored the feasibility of an exact approach and presented the first tractable solution (Opera) for the scaffolding problem. In comparison with existing scaffolders, Opera produces longer and more accurate scaffolds, demonstrating the utility and advantage of an exact approach. Secondly, I presented a formal definition for in silico assembly validation and finishing, and explored the feasibility of an exact solution (FinIS) using quadratic programming. Based on obtained results from several simulated and real datasets, we demonstrated that FinIS validates the correctness of a larger fraction of the assembly than existing ad hoc tools. Thirdly, I described several algorithmic and engineering refinements that can be applied to Opera, to achieve good scalability on large eukaryotic genomes. The results on large genomes demonstrate that OPERA-LG outperforms other state-of-the-art assemblers.