*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Carolyn Young
Summary Sentence: CSE Seminar: Scalable Algorithms for Complex Genome Assembly, Alignment, and Genetic Mapping By: Aydın Buluç
Full Summary: No summary paragraph submitted.
Aydın BuluçAbstract:
Genomes of eukaryotes are complex due to polyploidy, repetitions, and massive size. Genome assembly problem is at the heart of computational genomics. De novo genome assemblers typically output thousands of scaffolds without much information about their absolute and relative locations in the genome. High-density genetic linkage maps can be used to achieve chromosome-scale assembly by anchoring scaffolds to chromosomes if methods can be developed for producing linkage maps with millions of sequence-based markers.
In this talk, I will first present distributed-memory parallelization of de Bruijn graph construction and traversal, which is a key component of most de novo genome assemblers. Results show unprecedented performance and efficient scaling on up to 15,360 cores of a Cray XC30 supercomputer, on human genome as well as the challenging wheat genome, with performance improvement from days to seconds.
Then, I will briefly talk about merAligner, a highly parallel sequence aligner that implements a seed-and-extend algorithm. Since merAligner employs parallelism in all of its components, especially the seed index construction, it is particularly useful for aligning contigs to reads within the context of de novo genome assembly.
I will conclude my talk by describing a fast linkage group construction algorithm for genetic mapping. Contrary to existing algorithms that scale quadratically in the number of markers, our approach exploits the underlying linear structure of chromosomes to avoid expensive comparisons between (quadratically) many pairs of markers. The resulting linkage groups (i.e., marker clusters) are highly concordant with computationally expensive quadratic calculations, but our improved scaling allows far denser maps to be constructed with minimal computation.
(components are joint work with E. Georganas, V. Strnadova, J. Chapman, L. Oliker, J. Gonzalez, S. Jegelka, J. Gilbert, D. Rokhsar, K. Yelick)
Bio
Aydın Buluç is a research scientist at the Computational Research Division of the Lawrence Berkeley National Laboratory (LBNL). His research interests include parallel computing, combinatorial scientific computing, high performance graph analysis, sparse matrix computations, computational genomics and neuroscience. Previously, he was a Luis W. Alvarez postdoctoral fellow at LBNL and a visiting scientist at the Simons Institute for the Theory of Computing. He received his PhD in Computer Science from the University of California, Santa Barbara in 2010 and his BS in Computer Science and Engineering from Sabanci University, Turkey in 2005. Dr. Buluç is the recipient of a DOE Early Career Award in 2013. He is also a founding associate editor of the ACM Transactions on Parallel Computing. As a graduate student, he spent a semester at the Mathematics Department of MIT, and a summer at the CSRI institute of Sandia National Labs, in New Mexico. Dr. Buluç is a member of the SIAM and the ACM.
