Journal
BMC BIOINFORMATICS
Volume 12, Issue -, Pages -Publisher
BMC
DOI: 10.1186/1471-2105-12-238
Keywords
-
Categories
Funding
- National Science Foundation [EF0849615, CCF1048261]
- Natural Science Funding of Tianjin for Scholarly Exchange
- Direct For Computer & Info Scie & Enginr
- Division of Computing and Communication Foundations [1048261] Funding Source: National Science Foundation
- Emerging Frontiers
- Direct For Biological Sciences [0849615] Funding Source: National Science Foundation
Ask authors/readers for more resources
Background: Although dozens of algorithms and tools have been developed to find a set of cis-regulatory binding sites called a motif in a set of intergenic sequences using various approaches, most of these tools focus on identifying binding sites that are significantly different from their background sequences. However, some motifs may have a similar nucleotide distribution to that of their background sequences. Therefore, such binding sites can be missed by these tools. Results: Here, we present a graph-based polynomial-time algorithm, MotifClick, for the prediction of cis-regulatory binding sites, in particular, those that have a similar nucleotide distribution to that of their background sequences. To find binding sites with length k, we construct a graph using some 2(k-1)-mers in the input sequences as the vertices, and connect two vertices by an edge if the maximum number of matches of the local gapless alignments between the two 2(k-1)-mers is greater than a cutoff value. We identify a motif as a set of similar k-mers from a merged group of maximum cliques associated with some vertices. Conclusions: When evaluated on both synthetic and real datasets of prokaryotes and eukaryotes, MotifClick outperforms existing leading motif-finding tools for prediction accuracy and balancing the prediction sensitivity and specificity in general. In particular, when the distribution of nucleotides of binding sites is similar to that of their background sequences, MotifClick is more likely to identify the binding sites than the other tools.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available