PhD Defense: Genome assembly and variant detection using emerging sequencing technologies and graph based methods

The increased availability of genomic data and the increased ease and lower costs of DNA sequencing have revolutionized biomedical research. One of the key steps in most bioinformatics analyses is the assembly of the genome sequence of an organism using the data generated from the sequencing machines. Despite the long length of sequences generated by third-generation sequencing technologies (tens of thousands of basepairs), the automated reconstruction of entire genomes continues to be a formidable computational task. Although long read technologies help in resolving highly repetitive regions, the contigs generated from long read assembly do not always span a complete chromosome or even an arm of the chromosome. Recently, new genomic technologies have been developed that can "bridge" across repeats or other genomic regions that are difficult to sequence or assemble and improve genome assemblies by "scaffolding" together large segments of the genome. The problem of scaffolding is important in the context of both single genome assembly of large eukaryotic genomes and in metagenomics where the goal is to assemble multiple genomes in a sample simultaneously. First, we describe SALSA2, a method we developed to use interaction frequency between any two loci in the genome obtained using Hi-C technology to scaffold fragmented eukaryotic genome assemblies into chromosomes. SALSA2 can be used with either short or long read assembly to generate highly contiguous and accurate chromosome level assemblies. Hi-C data are known to introduce small inversion errors in the assembly, so we included the assembly graph in the scaffolding process and used the sequence overlap information to correct the orientation errors. Next, we present our contributions in metagenomics. We developed a scaffolding and variant detection method "Metacarvel" for metagenomic datasets. Scaffolding metagenomes is complicated due to several factors such as the presence of inter-genomic repeats, coverage ambiguities, and polymorphic regions in the genomes. Variant detection is also difficult in metagenomes because the different genomes within these complex samples are not known beforehand. We showed that MetaCarvel was able to generate accurate scaffolds and find genome-wide variations de novo in metagenomic datasets.Finally, we present EDIT, a tool for clustering millions of DNA sequence fragments originating from the highly conserved 16s rRNA gene in bacteria. We extended classical Four Russians' speed up to banded sequence alignment and showed that our method clusters highly similar sequences efficiently. This method can also be used to remove duplicates or near duplicate sequences from a dataset.With the increasing data being generated in different genomic and metagenomic studies using emerging sequencing technologies, our software tools and algorithms are well timed with the need of the community.

Examining Committee:

Chair: Dr. Mihai Pop Dean's rep: Dr. Michael Cummings Members: Dr. Adam Phillippy Dr. Hector Corrada Bravo Dr. Max Leiserson Dr. Aravind Srinivasan