Skip to Main Content
Frequently Asked Questions
Submit an ETD
Global Search Box
Need Help?
Keyword Search
Participating Institutions
Advanced Search
School Logo
Files
File List
Liu%2c Yating Accepted Thesis 8-1-17 Su17.pdf (2.81 MB)
ETD Abstract Container
Abstract Header
Motif Selection via a Tabu Search Solution to the Set Cover Problem
Author Info
Liu, Yating
Permalink:
http://rave.ohiolink.edu/etdc/view?acc_num=ohiou1501626790431744
Abstract Details
Year and Degree
2017, Master of Science (MS), Ohio University, Computer Science (Engineering and Technology).
Abstract
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)
Pages
101 p.
Subject Headings
Bioinformatics
;
Computer Science
Keywords
motif selection
;
tabu search
;
set cover problem
Recommended Citations
Refworks
EndNote
RIS
Mendeley
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)
Abstract Footer
Document number:
ohiou1501626790431744
Download Count:
417
Copyright Info
© 2017, all rights reserved.
This open access ETD is published by Ohio University and OhioLINK.