PairMotif: A New Pattern-Driven Algorithm for Planted (l, d) DNA Motif Search

Motif search is a fundamental problem in bioinformatics with an important application in locating transcription factor binding sites (TFBSs) in DNA sequences. The exact algorithms can report all (l, d) motifs and find the best one under a specific objective function. However, it is still a challengi...

Full description

Bibliographic Details
Main Authors:	Yu, Qiang, Huo, Hongwei, Zhang, Yipu, Guo, Hongzhi
Format:	Online
Language:	English
Published:	Public Library of Science 2012
Online Access:	https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3485246/

id	pubmed-3485246
recordtype	oai_dc
spelling	pubmed-34852462012-11-01 PairMotif: A New Pattern-Driven Algorithm for Planted (l, d) DNA Motif Search Yu, Qiang Huo, Hongwei Zhang, Yipu Guo, Hongzhi Research Article Motif search is a fundamental problem in bioinformatics with an important application in locating transcription factor binding sites (TFBSs) in DNA sequences. The exact algorithms can report all (l, d) motifs and find the best one under a specific objective function. However, it is still a challenging task to identify weak motifs, since either a large amount of memory or execution time is required by current exact algorithms. A new exact algorithm, PairMotif, is proposed for planted (l, d) motif search (PMS) in this paper. To effectively reduce both candidate motifs and scanned l-mers, multiple pairs of l-mers with relatively large distances are selected from input sequences to restrict the search space. Comparisons with several recently proposed algorithms show that PairMotif requires less storage space and runs faster on most PMS instances. Particularly, among the algorithms compared, only PairMotif can solve the weak instance (27, 9) within 10 hours. Moreover, the performance of PairMotif is stable over the sequence length, which allows it to identify motifs in longer sequences. For the real biological data, experimental results demonstrate the validity of the proposed algorithm. Public Library of Science 2012-10-31 /pmc/articles/PMC3485246/ /pubmed/23119020 http://dx.doi.org/10.1371/journal.pone.0048442 Text en © 2012 Yu et al http://creativecommons.org/licenses/by/4.0/ This is an open-access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are properly credited.
repository_type	Open Access Journal
institution_category	Foreign Institution
institution	US National Center for Biotechnology Information
building	NCBI PubMed
collection	Online Access
language	English
format	Online
author	Yu, Qiang Huo, Hongwei Zhang, Yipu Guo, Hongzhi
spellingShingle	Yu, Qiang Huo, Hongwei Zhang, Yipu Guo, Hongzhi PairMotif: A New Pattern-Driven Algorithm for Planted (l, d) DNA Motif Search
author_facet	Yu, Qiang Huo, Hongwei Zhang, Yipu Guo, Hongzhi
author_sort	Yu, Qiang
title	PairMotif: A New Pattern-Driven Algorithm for Planted (l, d) DNA Motif Search
title_short	PairMotif: A New Pattern-Driven Algorithm for Planted (l, d) DNA Motif Search
title_full	PairMotif: A New Pattern-Driven Algorithm for Planted (l, d) DNA Motif Search
title_fullStr	PairMotif: A New Pattern-Driven Algorithm for Planted (l, d) DNA Motif Search
title_full_unstemmed	PairMotif: A New Pattern-Driven Algorithm for Planted (l, d) DNA Motif Search
title_sort	pairmotif: a new pattern-driven algorithm for planted (l, d) dna motif search
description	Motif search is a fundamental problem in bioinformatics with an important application in locating transcription factor binding sites (TFBSs) in DNA sequences. The exact algorithms can report all (l, d) motifs and find the best one under a specific objective function. However, it is still a challenging task to identify weak motifs, since either a large amount of memory or execution time is required by current exact algorithms. A new exact algorithm, PairMotif, is proposed for planted (l, d) motif search (PMS) in this paper. To effectively reduce both candidate motifs and scanned l-mers, multiple pairs of l-mers with relatively large distances are selected from input sequences to restrict the search space. Comparisons with several recently proposed algorithms show that PairMotif requires less storage space and runs faster on most PMS instances. Particularly, among the algorithms compared, only PairMotif can solve the weak instance (27, 9) within 10 hours. Moreover, the performance of PairMotif is stable over the sequence length, which allows it to identify motifs in longer sequences. For the real biological data, experimental results demonstrate the validity of the proposed algorithm.
publisher	Public Library of Science
publishDate	2012
url	https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3485246/
_version_	1611920312406900736

PairMotif: A New Pattern-Driven Algorithm for Planted (l, d) DNA Motif Search

Similar Items