Print

Zheleva, Elena M.

Computer Science

2005

MS

Pattern matching (using regular expressions) is widely used in computational biology, and searching through a database of character sequences can take a long time. In this thesis, we explore and evaluate alternative representations of the database of sequences using suffix trees for two types of query problems: 1) Decide whether a match exists, and 2) Find all matches to a given pattern. We propose a framework in which the first problem can be solved in a faster manner than previous solutions while not slowing down the solution of the second problem. We apply several heuristics both at the level of suffix tree creation resulting in modified tree representations, and at the regular expression matching level in which we search subtrees in a given predefined order by simulating a deterministic finite automaton that we create from the given regular expression. The focus of the work is to develop a method for faster retrieval of PROSITE motif (a restricted regular expression) matches from a protein sequence database. We show empirically the effectiveness of our solution using several real protein data sets. Our method can be applied to any problem which requires answering restricted regular expression queries on a flatfile string database.