|Title:||Combinatorial Methods for Nucleic Acid Alignment and Folding|
Department of Computer Science, University of British Columia
By definition every PhD proposal should be unique and I hope this case is no exception. In what follows, I provide two distinct, self-contained and seemingly unrelated proposals. Both are motivated by problems related to nucleic acids, and my interest lies in the underlying combinatorial challenges they present. First, I describe string alignment problems posed by next-generation sequencing (NGS) technology. The short term goals outlined in the future work section are well underway and have already benefited from a productive collaboration with the BC Cancer Research Center. I identify a number of interesting theoretical problems related to succinct text indexes motivated by this technology. These problems are interesting from a theoretical perspective, but their solution would have an immediate practical impact. Second, I describe the nucleic acid folding pathway problem and summarize our existing progress on determining problem complexity and elucidating efficient and exact algorithms. The problem is interesting for a number of practical and theoretical reasons and ties together research questions from graph theory and DNA computing.