Imagine that you have a string of characters, "A", that you wish to locate within a different string of characters, "B". Now consider that B is on the order of at least 10,000 times larger than A. Then consider that A may be spread may be spread all over B, even splitting letters in half. Finally, consider the possibility that any number of letters from any part of A may be missing or replaced, and that the algorithm must be faster than a brute-force approach. This is the problem that Gene-DNA sequencing algorithms wish to solve, and doing so is no easy task. This talk details multiple techniques for effective parallel programming, how they can be applied toward this complex string-matching problem, and walks through the steps to create an algorithm which has lead to potential breakthroughs in decreasing the running time for solving this problem. Topics include Problem Space Promotion, Shattered Control Flow, and Gene-DNA Sequencing.
Advised by Larry Snyder
CSE 203
Wednesday
April 2, 2008
3:30 - 4:20 pm