Michal Petrucha. Data Structures for Whole-Genome Alignments . Bachelor thesis, Comenius University in Bratislava, 2012. Supervised by Broňa Brejová.

Download preprint: 12konikth.pdf, 481Kb

Download from publisher: not available

Related web page: not available

Bibliography entry: BibTeX


In this thesis we design data structures for storing alignments of genomes
from multiple species. The goal is to efficiently map positions and regions
from one genome to another based on their evolutionary relationships. We
provide an overview of several known data structures for the rank and select
operations on binary strings and use these operations to design a solution
to our problem. We have then implemented this solution and measured its
performance on real data, comparing several variants of our data structure.
Compared to the mapping tool LiftOver, our implementation maps positions
more efficiently, but requires longer initialization times.
   Keywords: alignment, whole-genome alignment, position mapping, re-
gion mapping, rank, select