In Partial Fulfillment of the Requirements for the Degree of Doctor of Philosophy

Levent Albayrak

will defend his dissertation

Novel Alignment Based Clustering Algorithms for Pan Genome Analysis of Bacteria Species

Abstract

Understanding the basic rules of bacterial evolution and adaptation is critical in developing new anti-bacterial drugs, the use of bacteria in biotechnology applications as well as in combating undesired consequences of bacterial presence in industrial and environmental settings such as corrosion, product spoilage and degradation.

Accumulation of single nucleotide mutations beneficial (or neutral) for bacterial survival is a well-studied mechanism of bacterial adaptation which also reflects the time of species separation from a common ancestor (molecular clock hypothesis). The gene loss or gain due to horizontal gene transfer is another much more dynamic mechanism of bacterial adaptation. Using these mechanisms, bacteria can acquire new features such as virulence factors, locomotion ability (flagella), and heat or drug resistance.

A major functional characteristic of bacterial species is the presence of particular gene sets common to the species (co re genome) together with genes that are available to individual or groups of genomes (pan genome). The technical difficulties however, lie in how one can identify the same genes or gene families in evolutionarily distant organisms:

1. Identification of a sequence similarity threshold
2. Computational complexity of sequence clustering algorithms
3. Creation of a biologically meaningful cluster topology

In this work, we have developed methods to improve the quality and performance of gene clustering including heuristics free, novel sequence alignment algorithms able to cluster a large number of sequences significantly faster than traditional methods (a few days compared to months of computation) that permitting identification of appropriate similarity thresholds and formation of biologically meaningful cluster topology.

The developed algorithms were used to build a “functional similarity” tree of the species reflecting ge ne composition similarity. The performed analysis also identified co-appearance and avoidance patterns of genes in bacterial species. We have applied the proposed methods to 22 genomes from Bartonella spp. using 34,060 genes.

Date: Monday, July 18, 2016
Time: 10:00 AM
Place: HBS 302
Advisor: Dr. Ioannis Pavlidis, Dr. Yuriy Fofanov

Faculty, students, and the general public are invited.