Alignment of phylogenetically unambiguous indels for genome-wide phylogenetic analysis and detection of lateral gene transfer

The evolutionary histories of genomes and of individual genes are important for understanding the genetic basis of microbial physiology. Genes that have a different history than the rest of the genome due to lateral genetic transfer may provide insight into the unique abilities of closely related organisms, but also serve to disrupt inference of the history of organisms by common lineage. Inconsistent results in phylogenetic signal among different genes and derived by different methods illustrate the need for approaches that can utilize multiple genes and clarify phylogenetic signal across entire genomes. Phylogenetic inference based on models of nucleotide and amino acid substitutions has become the standard, but higher level markers such as conserved insertions and deletions (indels), may provide clearer results.;Indels appear as gaps in the alignment of sequences, but high levels of alignment errors associated with gaps have generally meant their exclusion from phylogenetic analysis. Efforts to use indels as phylogenetic characters have relied on the interpretation of single multiple alignments without objective criteria for evaluating phylogenetic ambiguity in such alignments.;A method is presented in this thesis for finding only those indels that are phylogenetically unambiguous by allowing a defined amount of alignment ambiguity. A set of pairwise dynamic programming alignments is constructed to directly test positions in multiple alignments for phylogenetic unambiguity, without enumerating all possible phylogenetic topologies. This allows for an efficient genome-wide assessment of indels appropriate for phylogenetic inference.;Indels are used to analyze the relationships between phyla of bacteria and between strains of the bacterial genus Shewanella, which is of interest for applications of bioremediation and environmental engineering. Phylogenetic inference based on indels results in a comparable description of the history of these organisms to that of traditional analysis on single genes and concatenated core proteins. Indels also provide an easily interpretable assessment of the instability of phylogenetic signal among particular relationships, and allow for the detection of recent lateral genetic transfer between strains of Shewanella. We find weak inconsistent signal between bacterial phyla indicative of significant lateral genetic transfer, and we discuss implications of the effective range of indels as phylogenetic characters.