A Knowledge-Based Framework for the Alignment of Prokaryotic Genomes

The comparison of prokaryotic genomes is an important analysis step in bioinformatics which can help to discover genes and their functions, regulatory mechanisms, and phylogenetic relationships. Alignments generated with tools available for this task commonly show a relative low coverage and sensitivity,since only strong local similarities (i.e., the longest similarities with thehighest similarity values) are integrated into the alignment. The reason is the high number of global mutations (e.g., rearrangements and duplications) which frequently occur in prokaryotes which causes ambiguity during the assignment of similar subsequences of the genomes. This thesis describes a new knowledge-based framework which integrates biological knowledge of prokaryotic genome architecture into the alignment process of whole genomes in order to increase its quality (i.e., sensitivity, coverage, and specificity). The approach validates local similarities found between a reference genome for which knowledge exists and a query genome for which knowledge is not necessarily available with respect to the genome architecture of the reference genome. The framework allows for a manual and a automatical integration of more knowledge of common genome architecture into the reference model. The application of the knowledge-based framework on the set of local similarities found with a relaxed similarity threshold can significantly increase the sensitivity and the coverage of the resulting alignment in comparison to other approaches while the specificity remains nearly as good as with a strict similarity value.