Speaker
Ragnar Groot Koerkamp
ETH Zurich
Topic
Exact global alignment using A*
Sequence alignment, i.e. computing the edit distance between two DNA sequences, has been at the core of computational biology for half a century. The classical O(n^2) Needleman-Wunsch algorithm is used a lot, but becomes inefficient for long sequences. We use the A* shortest path algorithm to solve pairwise alignment in near-linear time for sequences with up to 10% uniform divergence, resulting in over 300x speedup over state of the art aligners on long sequences.
Zoom-Link for online participation: https://cwi-nl.zoom.us/j/87542191297?pwd=QTIxYlNQUmQ5UTFKb0NSaVVsbGFJZz09
