My research focuses on computational models and algorithms for the study of genome assembly and genome evolution.

Genome Assembly

The de Bruijn graph approaches dominated genome assembly in the last decade and resulted in many software tools for assembling short and accurate reads (e.g., Illumina reads). The recent breakthroughs in assembling long error-prone reads (e.g., PacBio SMRT and Oxford Nanopore reads) were all based on the overlap-layout-consensus approach which requires all-against-all comparison of reads and remains computationally challenging.

We generalized de Bruijn graphs and designed the A-Bruijn assembler to assemble long error-prone reads. The A-Bruijn assembler directly uses long error-prone reads to build the A-Bruijn graph and produces assemblies from the A-Bruijn graph, and thus avoids error-correcting of individual reads through extensive pairwise alignments. The A-Bruijn assembler also utilizes a new error correction approach and generates highly accurate genome reconstructions.

The A-Bruijn graph model also benefits the classic de Bruijn graph model for assembling short and accurate reads. The A-Bruijn assembler, for the first time, allows one to automatically choose larger values of the k-mer size in high-coverage regions to reduce repeat collapsing and smaller values of the k-mer size in the low-coverage regions to avoid fragmentation of the de Bruijn graph. Moreover, in the case of error-free reads, the A-Bruijn graph does not require any parameter setup and can be constructed in linear time and space.

Genome Evolution

Comparative and phylogenetic studies have proved useful in a myriad of applications ranging from novel medicines to outbreak analysis. As whole genomes are sequenced at increasing rates, using genome rearrangements for phylogenetic analyses is attracting increasing interest, especially as researchers uncover links between genome rearrangements and various diseases. However, previous phylogenetic studies of genome rearrangements were limited to small collections of genomes, low-resolution data (i.e., small numbers of synteny blocks), oversimplified models (e.g., no segmental duplications) and lack an effective assessment of robustness.

We proposed various evolutionary models for genome rearrangements and designed algorithms for analyzing the process of whole-genome evolution. Combining these models and algorithms, we designed the first phylogenetic reconstruction tool that overcomes all of the above difficulties: it supports a general model of genomic evolution, is very accurate, scales as well as sequence-based approaches, is robust against typical assembly errors, and supports standard bootstrapping methods. Moreover, this tool allows one to go beyond the inference of evolutionary relationships, and to infer both large-scale changes and local changes in the phylogney as well as to reconstruct ancestral genomes.