Whole-genome shotgun sequencing is an experimental technique used for obtaining information about a genome’s sequence, whereby it is broken up into many short (possibly overlapping) segments whose sequence is then determined. A long-standing use of sequencing is in genome assembly – the problem of determining the sequence of an unknown genome, which plays a central role for the sequencing of novel species. However, even within the same species, the genomes of two individuals differ, and though these variations are relatively small, they account for the observed variation in phenotypes. A large portion of these are copy number variants (CNVs), or genomic segments which appear a different number of times in different individuals. The unifying theme of this thesis is the use of genome graphs for both CNV detection and genome assembly problems. Genome graphs, which have already been successfully used for alignment and assembly, capture the structure of a genome even when its sequence is not fully known, as with the case of sequencing data. In this thesis, we extend their uses in several ways, culminating in a method for CNV detection that is based on a novel genome graph model. First, we demonstrate how the double-stranded nature of DNA can be efficiently incorporated into genome graphs by using the technique of bidirected network flow. Furthermore, we show how genome graphs can be efficiently used for finding solutions that maximize the likelihood of the data, as opposed to the usual maximum parsimony approach. Finally, we show how genome graphs can be useful for CNV detection through a novel construction called the donor graph. These extensions are combined into a method for detecting CNVs, which we use on a Yoruban human individual, showing a high degree of accuracy and improvement over previous methods.

Whole-genome shotgun sequencing is an experimental technique used for obtaining information about a genome’s sequence, whereby it is broken up into many short (possibly overlapping) segments whose sequence is then determined. A long-standing use of sequencing is in genome assembly – the problem of determining the sequence of an unknown genome, which plays a central role for the sequencing of novel species. However, even within the same species, the genomes of two individuals differ, and though these variations are relatively small, they account for the observed variation in phenotypes. A large portion of these are copy number variants (CNVs), or genomic segments which appear a different number of times in different individuals. The unifying theme of this thesis is the use of genome graphs for both CNV detection and genome assembly problems. Genome graphs, which have already been successfully used for alignment and assembly, capture the structure of a genome even when its sequence is not fully known, as with the case of sequencing data. In this thesis, we extend their uses in several ways, culminating in a method for CNV detection that is based on a novel genome graph model. First, we demonstrate how the double-stranded nature of DNA can be efficiently incorporated into genome graphs by using the technique of bidirected network flow. Furthermore, we show how genome graphs can be efficiently used for finding solutions that maximize the likelihood of the data, as opposed to the usual maximum parsimony approach. Finally, we show how genome graphs can be useful for CNV detection through a novel construction called the donor graph. These extensions are combined into a method for detecting CNVs, which we use on a Yoruban human individual, showing a high degree of accuracy and improvement over previous methods.