PhD Defense by Tony Pan

Primary tabs

Title: Distributed Memory Building Blocks for Massive Biological Sequence Analysis   Tony C. Pan School of Computational Science and Engineering College of Computing Georgia Institute of Technology   Date: Monday, March 27th, 2018 Time: 11:00am - 1:00pm Location: Klaus 1202   Committee: Dr. Srinivas Aluru (Advisor, School of Computational Science and Engineering, Georgia Tech) Dr. David Bader (School of Computational Science and Engineering, Georgia Tech) Dr. Umit Catalyurek (School of Computational Science and Engineering, Georgia Tech) Dr. King Jordan (School of Biology, Georgia Tech) Dr. Fredrick Vannberg (School of Biology, Georgia Tech) Dr. Richard Vuduc (School of Computational Science and Engineering, Georgia Tech)   Abstract:   K-mer indices and de Bruijn graphs are important data structures in bioinformatics with multiple applications ranging from foundational tasks such as error correction, alignment, and genome assembly, to knowledge discovery tasks including repeat detection and SNP identification.  While advances in next generation sequencing technologies have dramatically reduced the cost and improved latency and throughput, few bioinformatics tools can efficiently process the data sets at the current generation rate of 1.8 terabases every 3 days.   The volume and velocity with which sequencing data is generated necessitate efficient algorithms and implementation of k-mer indices and de Bruijn graphs, two central components in bioinformatic applications.  Existing applications that utilize k-mer counting and de Bruijn graphs, however, tend to provide embedded, specialized implementations.  The research presented here represents efforts toward the creation of the first reusable, flexible, and extensible distributed memory parallel libraries for k-mer indexing and de Bruijn graphs. These libraries are intended for simplifying the development of bioinformatics applications for distributed memory environments.  For each library, our goals were to create a set of API that are simple to use, and provide optimized implementations based on efficient parallel algorithms.  We designed algorithms that minimize communication volume and latency, and developed implementations with better cache utilization and SIMD vectorization.   We present Kmerind, a k-mer counting and indexing library based on distributed memory hash table and distributed sorted arrays, that provide efficient construction, query, and update operations. For de Bruijn graphs, we developed Bruno by leveraging Kmerind functionalities to support parallel de Bruijn graph construction, chain compaction, error removal, and graph traversal and element query.  We present the performance and scalability of Kmerind and Bruno in shared memory and distributed memory settings, and compare their performance to existing state-of-the-art tools.  


  • Workflow Status: Published
  • Created By: Tatianna Richardson
  • Created: 03/21/2018
  • Modified By: Tatianna Richardson
  • Modified: 03/21/2018