Methodologies for comparative genomics and metagenomics

The first part of this dissertation discusses the comparative analysis of the ENCODE pilot project, a nationwide project set out to analyze a set of regions totaling 1% of the human genome. For this project, DNA sequence alignments were generated between human and 27 other species; these alignments were then used to annotate the human sequence for evolutionarily constrained elements. Various teams (including ours) contributed with different alignment and constrain detection methodologies, each with different strengths and weaknesses. After all computational results were reconciled, consensus constrained elements were compared against experimental annotations from biological assays, which revealed how limited our current understanding of the human genome is.;The second part discusses a novel multi-species DNA alignment methodology based on a bipartite graph covering formulation, which allows for DNA sequence duplications in any of the species, while avoiding a combinatorial explosion of the number of alignments in the output.;Lastly, the third part discusses an application of comparative genomics for a pilot study regarding Cyanobacteria in the hot springs of Yellowstone National Park. In this study, DNA sequence alignments were used to enable targeted gene amplification from environmental samples, and gene sequences were compared across different temperature samples to locate trends related to thermal adaptation.