Efficient Design of Compact Unstructured RNA Libraries Covering All k-mers
Identifieur interne : 000099 ( Pmc/Curation ); précédent : 000098; suivant : 000100Efficient Design of Compact Unstructured RNA Libraries Covering All k-mers
Auteurs : Yaron Orenstein ; Bonnie BergerSource :
- Journal of Computational Biology [ 1066-5277 ] ; 2016.
Abstract
Url:
DOI: 10.1089/cmb.2015.0179
PubMed: 26713687
PubMed Central: 4752187
Links toward previous steps (curation, corpus...)
- to stream Pmc, to step Corpus: Pour aller vers cette notice dans l'étape Curation :000099
Links to Exploration step
PMC:4752187Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Efficient Design of Compact Unstructured RNA Libraries Covering All
<italic>k</italic>
-mers</title>
<author><name sortKey="Orenstein, Yaron" sort="Orenstein, Yaron" uniqKey="Orenstein Y" first="Yaron" last="Orenstein">Yaron Orenstein</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
</author>
<author><name sortKey="Berger, Bonnie" sort="Berger, Bonnie" uniqKey="Berger B" first="Bonnie" last="Berger">Bonnie Berger</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff2"></nlm:aff>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PMC</idno>
<idno type="pmid">26713687</idno>
<idno type="pmc">4752187</idno>
<idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC4752187</idno>
<idno type="RBID">PMC:4752187</idno>
<idno type="doi">10.1089/cmb.2015.0179</idno>
<date when="2016">2016</date>
<idno type="wicri:Area/Pmc/Corpus">000099</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000099</idno>
<idno type="wicri:Area/Pmc/Curation">000099</idno>
<idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Curation">000099</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">Efficient Design of Compact Unstructured RNA Libraries Covering All
<italic>k</italic>
-mers</title>
<author><name sortKey="Orenstein, Yaron" sort="Orenstein, Yaron" uniqKey="Orenstein Y" first="Yaron" last="Orenstein">Yaron Orenstein</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
</author>
<author><name sortKey="Berger, Bonnie" sort="Berger, Bonnie" uniqKey="Berger B" first="Bonnie" last="Berger">Bonnie Berger</name>
<affiliation><nlm:aff id="aff1"></nlm:aff>
</affiliation>
<affiliation><nlm:aff id="aff2"></nlm:aff>
</affiliation>
</author>
</analytic>
<series><title level="j">Journal of Computational Biology</title>
<idno type="ISSN">1066-5277</idno>
<idno type="eISSN">1557-8666</idno>
<imprint><date when="2016">2016</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><title>Abstract</title>
<p><bold>Current microarray technologies to determine RNA structure or measure
protein–RNA interactions rely on single-stranded, unstructured RNA probes
on a chip covering together all <italic>k</italic>
-mers. Since space on the array
is limited, the problem is to efficiently design a compact library of unstructured
<italic>ℓ</italic>
-long RNA probes, where each <italic>k</italic>
-mer is
covered at least <italic>p</italic>
times. Ray et al. designed such a library for
specific values of <italic>k</italic>
, <italic>ℓ</italic>
, and
<italic>p</italic>
using ad-hoc rules. To our knowledge, there is no general
method to date to solve this problem. Here, we address the problem of finding a
minimum-size covering of all <italic>k</italic>
-mers by
<italic>ℓ</italic>
-long sequences with the desired properties for any value
of <italic>k</italic>
, <italic>ℓ,</italic>
and <italic>p</italic>
. As we
prove that the problem is NP-hard, we give two solutions: the first is a greedy
algorithm with a logarithmic approximation ratio; the second, a heuristic greedy
approach based on random walks in de Bruijn graphs. The heuristic algorithm works
well in practice and produces a library of unstructured RNA probes that is only
∼1.1-times greater in size compared to the theoretical lower bound. We
present results for typical values of <italic>k</italic>
and probe lengths
<italic>ℓ</italic>
and show that our algorithm generates a library that
is significantly smaller than the library of Ray et al.; moreover, we show that
our algorithm outperforms naive methods. Our approach can be generalized and
extended to generate RNA or DNA oligo libraries with other desired properties. The
software is freely available online.</bold>
</p>
</div>
</front>
<back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Alhakim, A" uniqKey="Alhakim A">A. Alhakim</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Berger, B" uniqKey="Berger B">B. Berger</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Berger, M F" uniqKey="Berger M">M.F. Berger</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Berman, P" uniqKey="Berman P">P. Berman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Burgess, D J" uniqKey="Burgess D">D.J. Burgess</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Churkin, A" uniqKey="Churkin A">A. Churkin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="De Bruijn, N" uniqKey="De Bruijn N">N. de Bruijn</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Fordyce, P M" uniqKey="Fordyce P">P.M. Fordyce</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Fu, X D" uniqKey="Fu X">X.-D. Fu</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Gerstberger, S" uniqKey="Gerstberger S">S. Gerstberger</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Grossman, T" uniqKey="Grossman T">T. Grossman</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Hurd, W J" uniqKey="Hurd W">W.J. Hurd</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kertesz, M" uniqKey="Kertesz M">M. Kertesz</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kertesz, M" uniqKey="Kertesz M">M. Kertesz</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kierzek, E" uniqKey="Kierzek E">E. Kierzek</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kierzek, R" uniqKey="Kierzek R">R. Kierzek</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Konig, J" uniqKey="Konig J">J. König</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Kudla, G" uniqKey="Kudla G">G. Kudla</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lambert, N" uniqKey="Lambert N">N. Lambert</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lempel, A" uniqKey="Lempel A">A. Lempel</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Levin, A" uniqKey="Levin A">A. Levin</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Lorenz, R" uniqKey="Lorenz R">R. Lorenz</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Macwilliams, F J" uniqKey="Macwilliams F">F.J. MacWilliams</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Mandir, J B" uniqKey="Mandir J">J.B. Mandir</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Orenstein, Y" uniqKey="Orenstein Y">Y. Orenstein</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Philippakis, A A" uniqKey="Philippakis A">A.A. Philippakis</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ray, D" uniqKey="Ray D">D. Ray</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Ray, D" uniqKey="Ray D">D. Ray</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Rinn, J L" uniqKey="Rinn J">J.L. Rinn</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Steffen, P" uniqKey="Steffen P">P. Steffen</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Stefl, R" uniqKey="Stefl R">R. Stefl</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="Wan, Y" uniqKey="Wan Y">Y. Wan</name>
</author>
</analytic>
</biblStruct>
<biblStruct><analytic><author><name sortKey="West, D B" uniqKey="West D">D.B. West</name>
</author>
</analytic>
</biblStruct>
</listBibl>
</div1>
</back>
</TEI>
<pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">J Comput Biol</journal-id>
<journal-id journal-id-type="iso-abbrev">J. Comput. Biol</journal-id>
<journal-id journal-id-type="publisher-id">cmb</journal-id>
<journal-title-group><journal-title>Journal of Computational Biology</journal-title>
</journal-title-group>
<issn pub-type="ppub">1066-5277</issn>
<issn pub-type="epub">1557-8666</issn>
<publisher><publisher-name>Mary Ann Liebert, Inc.</publisher-name>
<publisher-loc>140 Huguenot Street, 3rd FloorNew Rochelle, NY 10801USA</publisher-loc>
</publisher>
</journal-meta>
<article-meta><article-id pub-id-type="pmid">26713687</article-id>
<article-id pub-id-type="pmc">4752187</article-id>
<article-id pub-id-type="publisher-id">10.1089/cmb.2015.0179</article-id>
<article-id pub-id-type="doi">10.1089/cmb.2015.0179</article-id>
<article-categories><subj-group subj-group-type="heading"><subject>Research Articles</subject>
</subj-group>
</article-categories>
<title-group><article-title>Efficient Design of Compact Unstructured RNA Libraries Covering All
<italic>k</italic>
-mers</article-title>
</title-group>
<contrib-group><contrib contrib-type="author"><name><surname>Orenstein</surname>
<given-names>Yaron</given-names>
</name>
<xref ref-type="aff" rid="aff1"><sup>1</sup>
</xref>
</contrib>
<contrib contrib-type="author" corresp="yes"><name><surname>Berger</surname>
<given-names>Bonnie</given-names>
</name>
<xref ref-type="aff" rid="aff1"><sup>1,</sup>
</xref>
<xref ref-type="aff" rid="aff2"><sup>2</sup>
</xref>
</contrib>
<aff id="aff1"><label><sup>1</sup>
</label>
Computer Science and Artificial Intelligence Laboratory,<institution>Massachusetts Institute of Technology</institution>
, Cambridge, MA.</aff>
<aff id="aff2"><label><sup>2</sup>
</label>
Department of Mathematics,<institution>Massachusetts Institute of Technology</institution>
, Cambridge, MA.</aff>
</contrib-group>
<author-notes><corresp><addr-line>Address correspondence to:</addr-line>
<addr-line><italic>Prof.
Bonnie Berger</italic>
</addr-line>
<addr-line><italic>Department of
Mathematics</italic>
</addr-line>
<institution><italic>Massachusetts Institute of
Technology</italic>
</institution>
<addr-line><italic>77 Mass Avenue,
2-373</italic>
</addr-line>
<addr-line><italic>Cambridge, MA
02139</italic>
</addr-line>
<italic>E-mail:</italic>
<email xlink:href="mailto:bab@mit.edu">bab@mit.edu</email>
</corresp>
</author-notes>
<pub-date pub-type="ppub"><day>01</day>
<month>2</month>
<year>2016</year>
<pmc-comment>string-date: February 2016</pmc-comment>
</pub-date>
<pub-date pub-type="pmc-release"><day>01</day>
<month>2</month>
<year>2016</year>
<pmc-comment>string-date: February 2016</pmc-comment>
</pub-date>
<pmc-comment> PMC Release delay is 0 months and 0 days and was based on the
. </pmc-comment>
<volume>23</volume>
<issue>2</issue>
<fpage>67</fpage>
<lpage>79</lpage>
<permissions><copyright-statement>© The Author(s) 2015; Published by Mary Ann Liebert,
Inc.</copyright-statement>
<copyright-year>2016</copyright-year>
<license license-type="open-access"><license-p>This Open Access article is distributed under the terms of the Creative
Commons License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/4.0">http://creativecommons.org/licenses/by/4.0</ext-link>
), which permits
unrestricted use, distribution, and reproduction in any medium, provided the
original work is properly credited.</license-p>
</license>
</permissions>
<self-uri content-type="pdf" xlink:type="simple" xlink:href="cmb.2015.0179.pdf"></self-uri>
<abstract><title>Abstract</title>
<p><bold>Current microarray technologies to determine RNA structure or measure
protein–RNA interactions rely on single-stranded, unstructured RNA probes
on a chip covering together all <italic>k</italic>
-mers. Since space on the array
is limited, the problem is to efficiently design a compact library of unstructured
<italic>ℓ</italic>
-long RNA probes, where each <italic>k</italic>
-mer is
covered at least <italic>p</italic>
times. Ray et al. designed such a library for
specific values of <italic>k</italic>
, <italic>ℓ</italic>
, and
<italic>p</italic>
using ad-hoc rules. To our knowledge, there is no general
method to date to solve this problem. Here, we address the problem of finding a
minimum-size covering of all <italic>k</italic>
-mers by
<italic>ℓ</italic>
-long sequences with the desired properties for any value
of <italic>k</italic>
, <italic>ℓ,</italic>
and <italic>p</italic>
. As we
prove that the problem is NP-hard, we give two solutions: the first is a greedy
algorithm with a logarithmic approximation ratio; the second, a heuristic greedy
approach based on random walks in de Bruijn graphs. The heuristic algorithm works
well in practice and produces a library of unstructured RNA probes that is only
∼1.1-times greater in size compared to the theoretical lower bound. We
present results for typical values of <italic>k</italic>
and probe lengths
<italic>ℓ</italic>
and show that our algorithm generates a library that
is significantly smaller than the library of Ray et al.; moreover, we show that
our algorithm outperforms naive methods. Our approach can be generalized and
extended to generate RNA or DNA oligo libraries with other desired properties. The
software is freely available online.</bold>
</p>
</abstract>
<kwd-group kwd-group-type="author"><title><bold>Key words:</bold>
</title>
<kwd>de Bruijn graph</kwd>
<kwd>microarray library design</kwd>
<kwd>RNA secondary structure</kwd>
</kwd-group>
<counts><fig-count count="2"></fig-count>
<table-count count="4"></table-count>
<equation-count count="2"></equation-count>
<ref-count count="33"></ref-count>
<page-count count="13"></page-count>
</counts>
</article-meta>
</front>
</pmc>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Pmc/Curation
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000099 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Curation/biblio.hfd -nk 000099 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Pmc |étape= Curation |type= RBID |clé= PMC:4752187 |texte= Efficient Design of Compact Unstructured RNA Libraries Covering All k-mers }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Curation/RBID.i -Sk "pubmed:26713687" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Curation/biblio.hfd \ | NlmPubMed2Wicri -a MersV1
![]() | This area was generated with Dilib version V0.6.33. | ![]() |