Over the last few decades, phylogenetics has emerged as a very promising field, facilitating a comparative framework to explain the genetic relationships among all the living organisms on earth. These genetic relationships are typically represented by a bifurcating phylogenetic tree — the tree of life. Reconstructing a phylogenetic tree is one of the central tasks in evolutionary biology. The different evolutionary processes, such as gene duplications, gene losses, speciation, and lateral gene transfer events, make the phylogeny reconstruction task more difficult. However, with the rapid developments in sequencing technologies and availability of genome-scale sequencing data, give us the opportunity to understand these evolutionary processes in a more informed manner, and ultimately, enable us to reconstruct genes and species phylogenies more accurately. This thesis is an attempt to provide computational methods for phylogenetic inference and give tools to conduct genome-scale comparative evolutionary studies, such as detecting homologous sequences and inferring gene families. In the first project, we present FastPhylo as a software package containing fast tools for reconstructing distance-based phylogenies. It implements the previously published efficient algorithms for estimating a distance matrix from the input sequences and reconstructing an un-rooted Neighbour Joining tree from a given distance matrix. Results on simulated datasets reveal that FastPhylo can handles hundred of thousands of sequences in a minimum time and memory efficient manner. The easy to use, well-defined interfaces, and the modular structure of FastPhylo allows it to be used in very large Bioinformatic pipelines. In the second project, we present a synteny-aware gene homology method, called GenFamClust (GFC) that uses gene content and gene order conservation to detect homology. Results on simulated and biological datasets suggest that local synteny information combined with the sequence similarity improves the detection of homologs. In the third project, we introduce a novel phylogeny-based clustering method, PhyloGenClust, which partitions a very large gene family into smaller subfamilies. ROC (receiver operating characteristics) analysis on synthetic datasets show that PhyloGenClust identify subfamilies more accurately. PhyloGenClust can be used as a middle tier clustering method between raw clustering methods, such as sequence similarity methods, and more sophisticated Bayesian-based phylogeny methods. Finally, we introduce a novel probabilistic Bayesian method based on the DLTRS model, to sample reconciliations of a gene tree inside a species tree. The method uses MCMC framework to integrate LGTs, gene duplications, gene losses and sequence evolution under a relaxed molecular clock for substitution rates. The proposed sampling method estimates the posterior distribution of gene trees and provides the temporal information of LGT events over the lineages of a species tree. Analysis on simulated datasets reveal that our method performs well in identifying the true temporal estimates of LGT events. We applied our method to the genome-wide gene families for mollicutes and cyanobacteria, which gave an interesting insight into the potential LGTs highways. / <p>QC 20161010</p>

Lateral gene transfer (LGT) is an important factor contributing to the evolution of prokaryotic genomes. The Aquificae are a hyperthermophilic bacterial group whose genes show affiliations to many other lineages, including the hyperthermophilic Thermotogae, the Proteobacteria, and the Archaea. Here I outline these scenarios and consider the fit of the available data, including two recently sequenced genomes from members of the Aquificae, to different sets of predictions. Evidence from phylogenetic profiles and trees suggests that the ?-Proteobacteria have the strongest affinities with the three Aquificae analyzed. However, this phylogenetic signal is by no means the dominant one, with the Archaea, many lineages of thermophilic bacteria, and members of genus Clostridium and class ?-Proteobacteria also showing strong connections to the Aquificae. The phylogenetic affiliations of different functional subsystems showed strong biases: as observed previously, most but not all genes implicated in the core translational apparatus tended to group Aquificae with Thermotogae, while a wide range of metabolic systems strongly supported the Aquificae - ?-Proteobacteria link. Given the breadth of support for this latter relationship, a scenario of ?-proteobacterial ancestry coupled with frequent exchange among thermophilic lineages is a plausible explanation for the emergence of the Aquificae.

<p>Prokaryotes evolve, in part, by lateral gene transfer (LGT). This transfer of genetic material is likely important in the evolution of operons, a group of genes that are transcribed as a single mRNA. Genes that are transferred may then be integrated into genomes by homologous recombination. In this thesis, it was proposed that homologous recombination is the mechanism of integration of laterally transferred genes into operons. To investigate this proposal, a phylogenetic tree of Bacillus was inferred using DNA sequence alignments. LGT was inferred using a parsimony algorithm, and operons were inferred using OperonDB. Homologous recombination breakpoints were identified by permutation tests, <em>GENECONV</em> and maximum chi square algorithm. The results indicate that there is evidence for integration of functionally annotated genes into operons by homologous recombination. There are several laterally transferred genes that have recombination breakpoints before the start codon or after the stop codon of the genes. It was also proposed in this thesis that LGT causes an increase in the rate of evolution of genes that are neighbours of laterally transferred genes. To investigate this proposal, genes that are neighbours of laterally transferred genes in Bacillus were identified. These genes were classified as upstream or downstream genes to the LGT event. Genes that are not neighbours of laterally transferred genes were also identified as a control. Selection and the rate of evolution was studied using maximum likelihood models implemented in CodeML of PAML. Genes under positive selection were inferred using likelihood ratio tests. The results indicate that only a few neighbouring genes were under positive selection, and the rate of evolution of the neighbouring genes was slightly higher than that of the non-neighbouring genes. The high rates of evolution of the neighbouring genes are likely due to relaxed selection on the neighbouring genes.</p> / Master of Biological Science (MBioSci)

Yes / Several bacterial families are known to be highly abundant within the human microbiome, but their ecological roles and evolutionary histories have yet to be investigated in depth. One such family, Lachnospiraceae (phylum Firmicutes, class Clostridia) is abundant in the digestive tracts of many mammals and relatively rare elsewhere. Members of this family have been linked to obesity and protection from colon cancer in humans, mainly due to the association of many species within the group with the production of butyric acid, a substance that is important for both microbial and host epithelial cell growth. We examined the genomes of 30 Lachnospiraceae isolates to better understand the origin of butyric acid capabilities and other ecological adaptations within this group. Butyric acid production-related genes were detected in fewer than half of the examined genomes with the distribution of this function likely arising in part from lateral gene transfer (LGT). An investigation of environment-specific functional signatures indicated that human gut-associated Lachnospiraceae possess genes for endospore formation, whereas other members of this family lack key sporulation-associated genes, an observation supported by analysis of metagenomes from the human gut, oral cavity, and bovine rumen. Our analysis demonstrates that adaptation to an ecological niche and acquisition of defining functional roles within a microbiome can arise through a combination of both habitat-specific gene loss and LGT. / Canadian Institute for Health Research (grant number CMF-108026), Genome Atlantic and the Canada Research Chairs program to R.G.B.

Bacteria's ability to pass entire genes between one another, a process called Horizontal Gene Transfer (HGT), has a major impact on bacterial evolution. In an ongoing project at Harvey Mudd, computational methods have been used to catalogue the HGT events that have impacted a group of closely related bacteria. This thesis builds on that project, by improving our ability to identify gene families --- groups of genes in different strains that are related. Previously, similarity was measured only by comparing two genes' DNA sequences, ignoring their positions on the organism's DNA. Here, we leverage genes' relative position to make a better measurement of gene similarity. These improved similarity measurements will improve the existing pipeline's ability to identify HGT events.

<p>Bacterial resistance to antibiotics has become a serious problem. This is due to the remarkable ability of bacteria to respond and rapidly adapt to environmental changes. Integrons are elements with the capacity for gene capture by an integron-encoded site-specific recombinase called IntI. IntI binds and acts at the recombination sites, <i>attI </i>and<i> attC</i> resulting in excision and integration of short DNA elements called gene cassettes carrying an <i>attC</i> site in the 3’ end. Several families of antibiotic resistance genes are borne on gene cassettes in integrons connected to mobile elements. Other cassettes reside in the larger and ancestral superintegrons located on chromosomes in both pathogenic and environmental bacteria. Due to their close connection with lateral gene transfer systems, it is possible that integrons are functionally dependent on those networks. This work presents arguments for such connections. The<i> attC</i> of the <i>aadA1-qacE</i> cassette junction in Tn<i>21</i> was characterized in detail. Like other <i>attC</i> sites, it contains two pairs of inverted repeats and is almost palindromic. By using electrophoretic mobility shift assays, this study showed that IntI1 binds only to the bottom strand of <i>attC</i>. Upon folding the strand into a hairpin, a few chiral hairpin distortions define both the strand choice and also the appropriate orientation of the highly symmetrical site. Structural recognition also explains the wide sequence variation among <i>attC</i> sites. We have documented the initial cleavage step in recombination in IntI extracts and integrase levels in extracts were evaluated by a new method. Mutagenesis and homology modelling were performed to find amino acid residues in IntI1 that are important for recognition of <i>attC</i> hairpin-DNA. Comparisons were made with other tyrosine family members to explain how integron integrases differ in site-recognition and also in their mechanism of strand exchange.</p>

Bacterial resistance to antibiotics has become a serious problem. This is due to the remarkable ability of bacteria to respond and rapidly adapt to environmental changes. Integrons are elements with the capacity for gene capture by an integron-encoded site-specific recombinase called IntI. IntI binds and acts at the recombination sites, attI and attC resulting in excision and integration of short DNA elements called gene cassettes carrying an attC site in the 3’ end. Several families of antibiotic resistance genes are borne on gene cassettes in integrons connected to mobile elements. Other cassettes reside in the larger and ancestral superintegrons located on chromosomes in both pathogenic and environmental bacteria. Due to their close connection with lateral gene transfer systems, it is possible that integrons are functionally dependent on those networks. This work presents arguments for such connections. The attC of the aadA1-qacE cassette junction in Tn21 was characterized in detail. Like other attC sites, it contains two pairs of inverted repeats and is almost palindromic. By using electrophoretic mobility shift assays, this study showed that IntI1 binds only to the bottom strand of attC. Upon folding the strand into a hairpin, a few chiral hairpin distortions define both the strand choice and also the appropriate orientation of the highly symmetrical site. Structural recognition also explains the wide sequence variation among attC sites. We have documented the initial cleavage step in recombination in IntI extracts and integrase levels in extracts were evaluated by a new method. Mutagenesis and homology modelling were performed to find amino acid residues in IntI1 that are important for recognition of attC hairpin-DNA. Comparisons were made with other tyrosine family members to explain how integron integrases differ in site-recognition and also in their mechanism of strand exchange.

The genomes of the hemiascomycetes Saccharomyces cerevisiae and Ashbya gossypii have been completely sequenced, allowing a comparative analysis of these two genomes, which reveals that a small number of genes appear to have entered these genomes as a result of horizontal gene transfer from bacterial sources. One potential case of horizontal gene transfer in A. gossypii and 10 potential cases in S. cerevisiae were identified, of which two were investigated further. One gene, encoding the enzyme dihydroorotate dehydrogenase (DHOD), is potentially a case of horizontal gene transfer, as shown by sequencing of this gene from additional bacterial and fungal species to generate sufficient data to construct a well-supported phylogeny. The DHOD-encoding gene found in S. cerevisiae, URA1 (YKL216W), appears to have entered the Saccharomycetaceae after the divergence of the S. cerevisiae lineage from the Candida albicans lineage and possibly since the divergence from the A. gossypii lineage. This gene appears to have come from the Lactobacillales, and following its acquisition the endogenous eukaryotic DHOD gene was lost. It was also shown that the bacterially derived horizontally transferred DHOD is required for anaerobic synthesis of uracil in S. cerevisiae. The other gene discussed in detail is BDS1, an aryl- and alkyl-sulfatase gene of bacterial origin that we have shown allows utilization of sulfate from several organic sources. Among the eukaryotes, this gene is found in S. cerevisiae and Saccharomyces bayanus and appears to derive from the alpha-proteobacteria. / Dissertation

In this study, 59 epidemiologically unrelated Salmonella strains isolated from foods in T&uuml / rkiye and 49 Salmonella strains obtained from National Salmonella Reference Laboratories of Germany were analysed. For the characterization of strains, analyses such as serotyping, phage typing, antibiotyping and molecular biological characterization were done. The strains exhibited 17 different serotypes with S. Enteritidis serotype and PT21 phage type being the most prevalent in Turkish isolates. The highest antimicrobial resistance was observed against NAL for Turkish strains, whereas it was against SUL for strains from German origin. Molecular typing of all strains exhibited different plasmid profiles and PFGE patterns. There were 1-4 plasmids/profile for Turkish strains and 1-7 plasmids/profile for German strains. The PFGE patterns revealed 42 different subgroups, having two major clusters with 44,3% arbitrary homology. Among 72 resistant strains, the most prevalent resistance genotypes were observed as blatem-1 (%56, AMP resistance) / floR (%100, CHL and FFC resistance) / aphA1 (%100, KAN and NEO resistance) / tet(A) (%53, TET resistance) / aadA1 (%82, SPE and STR resistance) / sulI (%78, SUL resistance). The class I integron variable region analyses exhibited 700 bp (1 strain), 1000 bp (37 strain), 1200 bp (16 strain) and 1600 bp (3 strain) integrons.

Rampant lateral gene transfer (LGT) among prokaryotes, hybridization in plants and other reticulate evolutionary processes invalidate typical phylogenetic tree models by violating the assumption that organisms only inherit genetic information from a single parent species. Comparing the different evolutionary histories of multiple genes is necessary to identify and assess these processes. In this work I develop efficient approximation and fixed-parameter algorithms for computing rooted maximum agreement forests (MAFs) and maximum acyclic agreement forests (MAAFs) of pairs of phylogenetic trees. Their sizes correspond to the subtree-prune-and-regraft (SPR) distance and the hybridization number of these pairs of trees, which are important measures of the dissimilarity of phylogenies used in studying reticulate evolution. Although these MAFs and MAAFs are NP-hard to compute, my fixed-parameter algorithms are practical because they scale exponentially with the computed distance rather than the size of the trees. I contribute efficient fixed-parameter algorithms for computing MAFs and MAAFs of two binary rooted trees and give the first efficient fixed-parameter and approximation algorithms for computing MAFs of two multifurcating rooted trees. My open-source implementation of the MAF algorithms is orders of magnitude faster than previous approaches, reducing the time required to compute SPR distances of 46 between trees of 144 species to fractions of a second whereas previous approaches required hours to compute SPR distances of 25. These fast MAF-based distance metrics enable the construction of supertrees to reconcile a collection of gene trees and rapid inference of LGT. Simulations demonstrate that supertrees minimizing the SPR distance are more accurate than other supertree methods under plausible rates of LGT. I constructed an SPR supertree from a phylogenomic dataset of 40,631 gene trees covering 244 genomes from several major bacterial phyla and inferred "highways" of gene transfer between these bacterial classes and genera; a small number of these highways connect distantly related genera and can highlight specific genes implicated in long-distance LGT. These fast MAF algorithms are thus practical and enable new analyses of reticulate evolution.