April 8, 2019 –
Title: Efficient Algorithms for Motif Search and Related Problems
Ph.D. Candidate: Peng Xiao
Major Advisor: Dr. Sanguthevar Rajasekaran
Associate Advisors: Dr. Yufeng Wu, Dr. Sheida Nabavi
Day/Time: Monday, April 8, 2019 10:00 AM
Location: HBL 1947 Conference Room
Information extraction from voluminous biological data is a challenging problem. Motif search is a fundamental problem in this direction. This problem can be stated as that of finding patterns from different biological sequences. Motif search has many applications in solving some crucial biological problems. For example, finding DNA motifs is very important for the determination of open reading frames, identification of gene promoter elements, location of RNA degradation signals, and the identification of alternative splicing sites.
Many motif models have been proposed in the literature. In this thesis we focus on Planted Motif Search (PMS) and Edit-distance-based Motif Search (EMS) problems. Both problems are intractable. Although extensive studies have been carried out by previous researchers, existing PMS and EMS solvers still have their limitations in terms of solving large datasets and challenging instances. In this thesis, we offer efficient algorithms for PMS and EMS. We also propose a new model for motif search. In addition, we propose some novel speedup techniques for parallel singular value decomposition.