MersV1, Main, Exploration, bibRecord, 002225

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

Identifieur interne : 002225 ( Main/Exploration ); précédent : 002224; suivant : 002226

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

Auteurs : Qiang Yu ; Hongwei Huo ; Yipu Zhang ; Hongzhi Guo

Source :

PLoS ONE [ 1932-6203 ] ; 2012.

RBID : PMC:3485246

Descripteurs français

KwdFr :
- ADN (), Algorithmes, Biologie informatique (), Facteurs de transcription (métabolisme), Logiciel, Motifs nucléotidiques, Reconnaissance automatique des formes, Simulation numérique, Sites de fixation.
MESH :
- métabolisme : Facteurs de transcription.
- ADN, Algorithmes, Biologie informatique, Logiciel, Motifs nucléotidiques, Reconnaissance automatique des formes, Simulation numérique, Sites de fixation.

English descriptors

KwdEn :
- Algorithms, Binding Sites, Computational Biology (methods), Computer Simulation, DNA (chemistry), Nucleotide Motifs, Pattern Recognition, Automated, Software, Transcription Factors (metabolism).
MESH :
- chemical , chemistry : DNA.
- chemical , metabolism : Transcription Factors.
- methods : Computational Biology.
- Algorithms, Binding Sites, Computer Simulation, Nucleotide Motifs, Pattern Recognition, Automated, Software.

Abstract

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.

Url:

http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3485246

DOI: 10.1371/journal.pone.0048442
PubMed: 23119020
PubMed Central: 3485246

Affiliations:

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">PairMotif: A New Pattern-Driven Algorithm for Planted (<italic>l</italic>
, <italic>d</italic>
) DNA Motif Search</title>
<author><name sortKey="Yu, Qiang" sort="Yu, Qiang" uniqKey="Yu Q" first="Qiang" last="Yu">Qiang Yu</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
</author>
<author><name sortKey="Huo, Hongwei" sort="Huo, Hongwei" uniqKey="Huo H" first="Hongwei" last="Huo">Hongwei Huo</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
</author>
<author><name sortKey="Zhang, Yipu" sort="Zhang, Yipu" uniqKey="Zhang Y" first="Yipu" last="Zhang">Yipu Zhang</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
</author>
<author><name sortKey="Guo, Hongzhi" sort="Guo, Hongzhi" uniqKey="Guo H" first="Hongzhi" last="Guo">Hongzhi Guo</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">23119020</idno>
<idno type="pmc">3485246</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC3485246</idno>
<idno type="RBID">PMC:3485246</idno>
<idno type="doi">10.1371/journal.pone.0048442</idno>
<date when="2012">2012</date>
<idno type="wicri:Area/Pmc/Corpus">001075</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">001075</idno>
<idno type="wicri:Area/Pmc/Curation">001075</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">001075</idno>
<idno type="wicri:Area/Pmc/Checkpoint">001290</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Checkpoint">001290</idno>
<idno type="wicri:source">PubMed</idno>
<idno type="RBID">pubmed:23119020</idno>
<idno type="wicri:Area/PubMed/Corpus">001D38</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">001D38</idno>
<idno type="wicri:Area/PubMed/Curation">001D38</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">001D38</idno>
<idno type="wicri:Area/PubMed/Checkpoint">001C51</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">001C51</idno>
<idno type="wicri:Area/Ncbi/Merge">000A06</idno>
<idno type="wicri:Area/Ncbi/Curation">000A06</idno>
<idno type="wicri:Area/Ncbi/Checkpoint">000A06</idno>
<idno type="wicri:Area/Main/Merge">002250</idno>
<idno type="wicri:Area/Main/Curation">002225</idno>
<idno type="wicri:Area/Main/Exploration">002225</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">PairMotif: A New Pattern-Driven Algorithm for Planted (<italic>l</italic>
, <italic>d</italic>
) DNA Motif Search</title>
<author><name sortKey="Yu, Qiang" sort="Yu, Qiang" uniqKey="Yu Q" first="Qiang" last="Yu">Qiang Yu</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
</author>
<author><name sortKey="Huo, Hongwei" sort="Huo, Hongwei" uniqKey="Huo H" first="Hongwei" last="Huo">Hongwei Huo</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
</author>
<author><name sortKey="Zhang, Yipu" sort="Zhang, Yipu" uniqKey="Zhang Y" first="Yipu" last="Zhang">Yipu Zhang</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
</author>
<author><name sortKey="Guo, Hongzhi" sort="Guo, Hongzhi" uniqKey="Guo H" first="Hongzhi" last="Guo">Hongzhi Guo</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
</author>
</analytic>
<series><title level="j">PLoS ONE</title>
<idno type="eISSN">1932-6203</idno>
<imprint><date when="2012">2012</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term>
<term>Binding Sites</term>
<term>Computational Biology (methods)</term>
<term>Computer Simulation</term>
<term>DNA (chemistry)</term>
<term>Nucleotide Motifs</term>
<term>Pattern Recognition, Automated</term>
<term>Software</term>
<term>Transcription Factors (metabolism)</term>
</keywords>
<keywords scheme="KwdFr" xml:lang="fr"><term>ADN ()</term>
<term>Algorithmes</term>
<term>Biologie informatique ()</term>
<term>Facteurs de transcription (métabolisme)</term>
<term>Logiciel</term>
<term>Motifs nucléotidiques</term>
<term>Reconnaissance automatique des formes</term>
<term>Simulation numérique</term>
<term>Sites de fixation</term>
</keywords>
<keywords scheme="MESH" type="chemical" qualifier="chemistry" xml:lang="en"><term>DNA</term>
</keywords>
<keywords scheme="MESH" type="chemical" qualifier="metabolism" xml:lang="en"><term>Transcription Factors</term>
</keywords>
<keywords scheme="MESH" qualifier="methods" xml:lang="en"><term>Computational Biology</term>
</keywords>
<keywords scheme="MESH" qualifier="métabolisme" xml:lang="fr"><term>Facteurs de transcription</term>
</keywords>
<keywords scheme="MESH" xml:lang="en"><term>Algorithms</term>
<term>Binding Sites</term>
<term>Computer Simulation</term>
<term>Nucleotide Motifs</term>
<term>Pattern Recognition, Automated</term>
<term>Software</term>
</keywords>
<keywords scheme="MESH" xml:lang="fr"><term>ADN</term>
<term>Algorithmes</term>
<term>Biologie informatique</term>
<term>Logiciel</term>
<term>Motifs nucléotidiques</term>
<term>Reconnaissance automatique des formes</term>
<term>Simulation numérique</term>
<term>Sites de fixation</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><p>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 (<italic>l</italic>
, <italic>d</italic>
) 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 (<italic>l</italic>
, <italic>d</italic>
) motif search (PMS) in this paper. To effectively reduce both candidate motifs and scanned <italic>l</italic>
-mers, multiple pairs of <italic>l</italic>
-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.</p>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Lawrence, Ce" uniqKey="Lawrence C">CE Lawrence</name>
</author>
<author><name sortKey="Altschul, Sf" uniqKey="Altschul S">SF Altschul</name>
</author>
<author><name sortKey="Boguski, Ms" uniqKey="Boguski M">MS Boguski</name>
</author>
<author><name sortKey="Liu, Js" uniqKey="Liu J">JS Liu</name>
</author>
<author><name sortKey="Neuwald, Af" uniqKey="Neuwald A">AF Neuwald</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Buhler, J" uniqKey="Buhler J">J Buhler</name>
</author>
<author><name sortKey="Tompa, M" uniqKey="Tompa M">M Tompa</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Fratkin, E" uniqKey="Fratkin E">E Fratkin</name>
</author>
<author><name sortKey="Naughton, Bt" uniqKey="Naughton B">BT Naughton</name>
</author>
<author><name sortKey="Brutlag, Dl" uniqKey="Brutlag D">DL Brutlag</name>
</author>
<author><name sortKey="Batzoglou, S" uniqKey="Batzoglou S">S Batzoglou</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Bi, Cp" uniqKey="Bi C">CP Bi</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Huang, Cw" uniqKey="Huang C">CW Huang</name>
</author>
<author><name sortKey="Lee, Ws" uniqKey="Lee W">WS Lee</name>
</author>
<author><name sortKey="Hsieh, Sy" uniqKey="Hsieh S">SY Hsieh</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Evans, Pa" uniqKey="Evans P">PA Evans</name>
</author>
<author><name sortKey="Smith, A" uniqKey="Smith A">A Smith</name>
</author>
<author><name sortKey="Wareham, Ht" uniqKey="Wareham H">HT Wareham</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Eskin, E" uniqKey="Eskin E">E Eskin</name>
</author>
<author><name sortKey="Pevzner, Pa" uniqKey="Pevzner P">PA Pevzner</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Marsan, L" uniqKey="Marsan L">L Marsan</name>
</author>
<author><name sortKey="Sagot, Mf" uniqKey="Sagot M">MF Sagot</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Davila, J" uniqKey="Davila J">J Davila</name>
</author>
<author><name sortKey="Balla, S" uniqKey="Balla S">S Balla</name>
</author>
<author><name sortKey="Rajasekaran, S" uniqKey="Rajasekaran S">S Rajasekaran</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Bulyk, Ml" uniqKey="Bulyk M">ML Bulyk</name>
</author>
<author><name sortKey="Johnson, Pfl" uniqKey="Johnson P">PFL Johnson</name>
</author>
<author><name sortKey="Church, Gm" uniqKey="Church G">GM Church</name>
</author>
</analytic>
</biblStruct>
<biblStruct></biblStruct>
<biblStruct></biblStruct>
<biblStruct><analytic><author><name sortKey="Liu, X" uniqKey="Liu X">X Liu</name>
</author>
<author><name sortKey="Brutlag, Dl" uniqKey="Brutlag D">DL Brutlag</name>
</author>
<author><name sortKey="Liu, Js" uniqKey="Liu J">JS Liu</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Pavesi, G" uniqKey="Pavesi G">G Pavesi</name>
</author>
<author><name sortKey="Mauri, G" uniqKey="Mauri G">G Mauri</name>
</author>
<author><name sortKey="Pesole, G" uniqKey="Pesole G">G Pesole</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Tompa, M" uniqKey="Tompa M">M Tompa</name>
</author>
<author><name sortKey="Li, N" uniqKey="Li N">N Li</name>
</author>
<author><name sortKey="Bailey, Tl" uniqKey="Bailey T">TL Bailey</name>
</author>
<author><name sortKey="Church, Gm" uniqKey="Church G">GM Church</name>
</author>
<author><name sortKey="Moor, Bd" uniqKey="Moor B">BD Moor</name>
</author>
</analytic>
</biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<affiliations><list></list>
<tree><noCountry><name sortKey="Guo, Hongzhi" sort="Guo, Hongzhi" uniqKey="Guo H" first="Hongzhi" last="Guo">Hongzhi Guo</name>
<name sortKey="Huo, Hongwei" sort="Huo, Hongwei" uniqKey="Huo H" first="Hongwei" last="Huo">Hongwei Huo</name>
<name sortKey="Yu, Qiang" sort="Yu, Qiang" uniqKey="Yu Q" first="Qiang" last="Yu">Qiang Yu</name>
<name sortKey="Zhang, Yipu" sort="Zhang, Yipu" uniqKey="Zhang Y" first="Yipu" last="Zhang">Yipu Zhang</name>
</noCountry>
</tree>
</affiliations>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Main/Exploration

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002225 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002225 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Sante
   |area=    MersV1
   |flux=    Main
   |étape=   Exploration
   |type=    RBID
   |clé=     PMC:3485246
   |texte=   PairMotif: A New Pattern-Driven Algorithm for Planted (l, d) DNA Motif Search
}}

Pour générer des pages wiki

HfdIndexSelect -h $EXPLOR_AREA/Data/Main/Exploration/RBID.i   -Sk "pubmed:23119020" \
       | HfdSelect -Kh $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd   \
       | NlmPubMed2Wicri -a MersV1

This area was generated with Dilib version V0.6.33.
Data generation: Mon Apr 20 23:26:43 2020. Site generation: Sat Mar 27 09:06:09 2021

Serveur d'exploration MERS

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

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

Source :

Descripteurs français

English descriptors

Abstract

Links toward previous steps (curation, corpus...)

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri

Pour générer des pages wiki

	Serveur d'exploration MERS
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.