Final Results
DNA Sequence Alignment with the Burrows Wheeler Transform
Advisor: Layla Oesper
Background
Human DNA can be interpreted as a string on the character set A,C,G and T, representing the different bases or nucleotides in DNA. In total, a human’s genome contains over 3 billion such characters. When a person’s genome is sequenced, we don’t get a complete picture of their genetic code. Instead, what we obtain are many millions or billions of short strings (~200-1000 characters), with some noise, that exist somewhere in their genome. To make sense of this data, these short reads are aligned to an existing reference genome, which is a representation of an idealized member of the species created from sequences from multiple individuals. Alignments of reads are not always perfect. A read may contain mismatches relative to the reference, or be missing subsequences that exist in the reference, or contain extra sequences that do not exist in the reference. Given the size of the reference genome (> 3 billion characters) and the number of reads to align (millions-billions), this means alignment is a computationally and algorithmically challenging problem.
The Burrows Wheeler Transform (BWT) is a compression technique (allows for the storage of data in less space) on strings that has been used in a number of different domains. For instance, it is the algorithm used in the bzip2 file compression program. The BWT is particularly useful when the string to be compressed is repetitive - a key feature of human DNA. A number of algorithms have been proposed that build upon the BWT to efficiently align short DNA sequences to a reference genome.
The project
In this project you will investigate the Burrows Wheeler Transform (BWT) and its application to short read DNA alignment. In particular you will:
- Understand the BWT (and the closely related FM-index) including how and why it works as a compression technique.
- Understand what a reference genome is and how it is created. Also, be aware of ethical and bias related considerations around the use of a reference genome.
- Understand how existing BWT based short read aligners work and be able to run them and correctly interpret their output. This also includes comparing the output of different existing aligners.
- Implement parts of the BWT and its use for alignment of short reads. The logical place to start is to use the BWT to look for exact read matches in the reference genome and then potentially add the ability to have mismatches or gaps.
- Identify existing datasets or create simulated datasets that can be used for testing alignment algorithms.
Recommended experience
Previous biology experience is NOT required for this project. Other courses that could be useful for this project include algorithms, and computational biology.
References/inspiration
Below are a few papers about existing work related to the BWT in DNA sequence aligners. These are only intended to provide you a minimal start for your literature search - they are certainly not the only nor necessarily the best sources for ideas. You will be finding and reading many additional papers!
- Li and Durbin. “Fast and accurate short read alignment with Burrows–Wheeler transform.” Bioinformatics. 2009 Jul 15; 25(14): 1754–1760.
- Langmead et al. “Ultrafast and memory-efficient alignment of short DNA sequences to the human genome.” Genome Biology volume 10, Article number: R25 (2009).
Meeting Time(s)
Fall Term, MWF 5A