Search Results (1 - 2 of 2 Results)

Sort By  
Sort Dir
 
Results per page  

Liu, YatingMotif Selection via a Tabu Search Solution to the Set Cover Problem
Master of Science (MS), Ohio University, 2017, Computer Science (Engineering and Technology)
Transcription factors (TFs) regulate gene expression through interaction with specific DNA regions, called transcription factor binding sites (TFBSs). Identifying TFBSs can help in understanding the mechanisms of gene regulation and the biology of human diseases. Motif discovery is the traditional method for discovering TFBSs. However, current motif discovery tools tend to generate a number of motifs that is too large to permit a biological validation. To address this problem, the motif selection problem is introduced. The aim of the motif selection problem is to select a small set of motifs from the discovered motifs, which cover a high percentage of genomic input sequences. Tabu search, a metaheuristic search method based on local search, is introduced to solve the motif selection problem. The performance of the proposed three motif selection methods, tabu-SCP, tabu-PSC and tabu-PNPSC, were evaluated by applying them to ChIP-seq data from the ENCyclopedia of DNA Elements (ENCODE) project. Motif selection was performed on 46 factor groups which include 158 human ChIP-seq data sets. The results of the three motif selection methods were compared with Greedy, enrichment method and relax integer liner programming (RILP). Tabu-PNPSC selected the smallest set of motifs with the highest overall accuracy. The average number of selected motifs was 1.37 and the average accuracy was 72.47%. Tabu-PNPSC was used to identify putative regulatory element binding sites that are in response to the overproduction of small RNAs RyfA1 in the bacteria Shigella dysenteriae. Six motifs were selected by tabu-PNPSC and the overall accuracy was 75.5%.

Committee:

Lonnie Welch (Advisor)

Subjects:

Bioinformatics; Computer Science

Keywords:

motif selection; tabu search; set cover problem

Al-Ouran, RamiMotif Selection: Identification of Gene Regulatory Elements using Sequence Coverage Based Models and Evolutionary Algorithms
Doctor of Philosophy (PhD), Ohio University, 2015, Electrical Engineering & Computer Science (Engineering and Technology)
The accuracy of identifying transcription factor binding sites (motifs) has increased with the use of technologies such as chromatin immunoprecipitation followed by sequencing (ChIP-seq), but this accuracy remains low enough that bioinformaticians and biologists struggle in choosing the right methods for identifying such regulatory elements. Current motif discovery methods typically produce lengthy lists of putative transcription factor binding sites, and a significant challenge lies in how to mine these lists to select a manageable set of candidate sites for experimental validation. Additionally, despite the importance of covering large numbers of genomic sequences, current motif discovery methods do not consider the sequence coverage percentage. To address the aforementioned problems, the motif selection problem is introduced and solved using a coverage based model greedy algorithm and a multi-objective evolutionary algorithm. The motif selection problem aims to produce a concise list of significant motifs which is both accurate and covers a high percentage of the genomic input sequences. The proposed motif selection methods were evaluated using ChIP-seq data from the ENCyclopedia of DNA Elements (ENCODE) project. In addition, the proposed methods were used to identify putative transcription factor binding sites in two case studies: stage specific binding sites in Brugia malayi, and tissue specific binding sites in hydroxyproline-rich glycoprotein (HRGP) genes in Arabidopsis thaliana.

Committee:

Lonnie Welch (Advisor)

Subjects:

Bioinformatics; Computer Science

Keywords:

Motif selection; motif discovery; ENCODE