Hardware Acceleration And Algorithms For Genomic Sequence Alignment And Its Applications

While genome sequencing data continues to rise exponentially (80%/year), transistor performance scaling has considerably slowed down (3%/year). Domain-specific acceleration (DSA), which uses specialized hardware for accelerating a narrow domain of applications, is one of the few remaining approaches in computer architecture to continue to scale compute performance and efficiency to enable the vast potential of genomics data. The entire domain of genomics relies heavily on one fundamental algorithm — genome sequence alignment — with wide-ranging applications in medicine and comparative genomics. The first part of this dissertation presents our work on hardware acceleration of genome sequence alignment, particularly for two emerging, compute-intensive applications in genomics — long read assembly (Darwin co-processor) and whole-genome alignments (Darwin-WGA co-processor). The accelerators are based on hardware-software co-design, which modifies an existing algorithm in a way that provides massive speedup (1,000-10,000x) in specialized hardware without compromising, and sometimes even enhancing, the results for a biologist. The second part of this dissertation focuses on the applications whole-genome alignments to make novel biological discoveries. It presents a novel algorithm (ORCHID) to confidently identify the orthologous region of a reference gene in the query genome. ORCHID is further used to develop a novel screen (hcoErosions) to discover hundreds of genes that are surprisingly lost in different mammals, some of which are considered indispensable in human and mouse. It also presents a novel screen we developed for testing the molecular basis of convergent evolution in mammals that also relied on our ORCHID algorithm.