November 19, 2018 –
Title: Efficient Algorithms for Motif Search and Related Problems
Ph.D. Candidate: Peng Xiao
Major Advisor: Dr. Sanguthevar Rajasekaran
Associate Advisors: Dr. Sheida Nabavi, Dr. Yufeng Wu
Date/Time: Monday, November 19, 2018 10:00am
Location: ITE 336
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 study we focus on Planted Motif Search (PMS) and Edit-distance-based Motif Search (EMS) problems. Both the 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 proposal, we offer efficient algorithms for PMS and EMS. Our algorithms are currently the state-of-the-art. We also propose a new model for motif search.