Motif Mining On Structured And Semi-structured Biological Data

Motif discovery in biological data is very important to biologists becausethey are conjectured to have biological significance. Despite the considerateeffort put in this topic, it remains a challenging and difficult problem.There are several advances in biology such that the data is structured (graphs)and semi-structured (sequences).A challenge of motif mining in sequences is the existence of variationsincluding substitutions and permutations. Taking into account the existenceof these two kinds of variations, we propose a novel sequential motif modeland devise an algorithm to discover those motifs. A reachability propertyis identified to prune the search space. We also demonstrate that the discoveredmotifs have biological significance. Motivated by another biologicalphenomenal called compensational mutation in biological sequences, we proposeanother model for motif discovery in biological sequences. Consideringcompensational mutation adds more degree of freedom in the search space.A novel algorithm is proposed to solve the problem. It is shown that theproposed algorithm can discover effective motifs in a timely manner.Besides sequential data, a huge amount of biological data can be naturallyrepresented as graphs, e.g., protein interaction networks and gene regulatorynetworks. Most of the existing graph mining research focuses on miningunweighted graphs. However, weighted graphs are actually more common. Toaddress the problem of motif discovery in weighted graphs, a weighted subgraphmotif model is proposed to capture the importance of a subgraph motifin a single large weighted graph. We study two related problems about subgraphmotif discovery in a large weighted graph: (1) discovering all motifs withrespect to a given minimum weight threshold and (2) finding top k motifs withthe largest weights. We identify a property called 1-extension property so thata bounded search can be achieved. Last but not least, real and synthetic datasets are used to show the effectiveness and efficiency of the proposed modeland algorithm.

Name thesis:degree_name

Doctor of Philosophy

Level thesis:degree_level

doctoral

Discipline thesis:degree_discipline

EECS - Computer and Information Sciences

Grantor dc:publisher

Case Western Reserve University School of Graduate Studies

Year dc:date

2013

Author dc:creator

• Su, Wei

Contributors dc:contributor

• Koyuturk, Mehmet
• Yang, Jiong

• Computer Science

Statement dc:rights

• unrestricted
• This thesis or dissertation is protected by copyright: all rights reserved. It may not be copied or redistributed beyond the terms of applicable copyright laws.

Language dc:language

English

Repository record dc:identifier

http://rave.ohiolink.edu/etdc/view?acc_num=case1365089538

OAI identifier oai:identifier

oai:etd.ohiolink.edu:case1365089538