Development and Exploration of Velvetrope: A Parallel, Bitwise Alignment Method on Biological Sequences
SESSION: Student Poster Reception
EVENT TYPE: Poster, ACM Student Poster
TIME: 5:15PM - 7:00PM
ABSTRACT: Next generation biological sequencing technologies have created a virtual torrent of new sequence data. The analysis challenges that this data presents needs to be addressed by new algorithms that are designed to be as efficient as possible and can scale with the data. One area of analytic interest is that of alignment, finding where two genetic sequences are similar. Finding these highly conserved regions can lead to new insights on how distantly related organisms perform related tasks. By examining all of the ways that nature has evolved solutions to a specific challenge, like synthesizing glucose, we can come up with new and efficient techniques for applications in everything from biofuels to medicine.
A novel alignment algorithm, Velvetrope, is introduced that is designed to be fast and parallel from the very beginning. It primarily uses only local bitwise operations is readily implemented on a GPU (Graphical Processing Unit). Velvetrope finds areas of high similarity between sequences and then aggregates this data across a set of sequences. The result is somewhere in between a local and multiple alignment and answers questions that neither can address independently.
In this poster the main components of Velvetrope will be explained and analyzed and the three implementations, in Python, C and CUDA, will be discussed. Each of these will be compared to each other as well as other similar algorithms like BLAST and HMMer for speed, scalability and accuracy.
[Velvetrope was co-developed during a summer internship at Los Alamos National Laboratory by myself, Joel Berendzen and Nick Hengartner. Coding the entire algorithm from start to finish was my first experience developing a large releasable program as well as working with GPU programming. The algorithm is further discussed in a recent BMC Bioinformatics article (submitted) and is freely available online.]