Skip to Main Content
 

Global Search Box

 
 
 

ETD Abstract Container

Abstract Header

Motif Selection via a Tabu Search Solution to the Set Cover Problem

Abstract Details

2017, Master of Science (MS), Ohio University, 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%.
Lonnie Welch (Advisor)
101 p.

Recommended Citations

Citations

  • Liu, Y. (2017). Motif Selection via a Tabu Search Solution to the Set Cover Problem [Master's thesis, Ohio University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1501626790431744

    APA Style (7th edition)

  • Liu, Yating. Motif Selection via a Tabu Search Solution to the Set Cover Problem. 2017. Ohio University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1501626790431744.

    MLA Style (8th edition)

  • Liu, Yating. "Motif Selection via a Tabu Search Solution to the Set Cover Problem." Master's thesis, Ohio University, 2017. http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1501626790431744

    Chicago Manual of Style (17th edition)