Alignment, Clustering and Extraction of Structured Motifs in DNA Promoter Sequences

<p>A simple motif is a short DNA sequence found in the promoter region and believed to act as a binding site for a transcription factor protein. A structured motif is a sequence of simple motifs (boxes) separated by short sequences (gaps). Biologists theorize that the presence of these motifs play a key role in gene expression regulation. Discovering these patterns is an important step towards understanding protein-gene and gene-gene interaction thus facilitates the building of accurate gene regulatory network models. DNA sequence motif extraction is an important problem in bioinformatics. Many studies have proposed algorithms to solve the problem instance of <em>simple motif</em> extraction. Only in the past decade has the more complex <em>structured motif extraction</em> problem been examined by researchers.</p> <p>The problem is inherently challenging as structured motif patterns are segmented into several boxes separated by variable size gaps for each instance. These boxes may not be exact copies, but may have multiple mismatched positions. The challenge is extenuated by the lack of resources for real datasets covering a wide range of possible cases. Also, incomplete annotation of real data leads to the discovery of unknown motifs that may be regarded as false positives. Furthermore, current algorithms demand unreasonable amount of prior knowledge to successfully extract the target pattern.</p> <p>The contributions of this research are four new algorithms. First, <em>SMGenerate</em> generates simulated datasets of implanted motifs that covers a wide range of biologically possible cases. Second, <em>SMAlign</em> aligns a pair of structured motifs optimally and efficiently given their gap constraints. Third, <em>SMCluster</em> produces multiple alignment of structured motifs through hierarchical clustering using SMAlign's affinity score. Finally, <em>SMExtract</em> extracts structured motifs from a set of sequences by using SMCluster to construct the target pattern from the top reported two-box patterns (fragments), extracted using an existing algorithm (Exmotif) and a two-box template. The main advantage of SMExtract is its efficiency to extract longer degenerate patterns while requiring less prior knowledge, about the pattern to be extracted, than current algorithms.</p>

Name thesis:degree_name

Doctor of Philosophy (PhD)

Level thesis:degree_level

Dissertation

Discipline thesis:degree_discipline

Electrical Engineering and Computer Science

Year

2012

Author dc:creator

• Alobaid, Faisal Abdulmalek

Contributors dc:contributor

• Kishan Mehrotra
• Chilukuri Mohan

• Branch and Bound Search
• Combinatorial Optimization
• Dynamic Programming
• Gap Constraints
• Multiple Sequence Alignment
• Structured Motif Extraction
• Computer Engineering

Repository record dc:identifier

https://surface.syr.edu/eecs_etd/322

OAI identifier oai:identifier

oai:surface.syr.edu:eecs_etd-1326