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