Reverse de Bruijn: Utilizing Reverse Peptide Synthesis to Cover All Amino Acid k-mers.
Identifieur interne : 002499 ( Ncbi/Merge ); précédent : 002498; suivant : 002500Reverse de Bruijn: Utilizing Reverse Peptide Synthesis to Cover All Amino Acid k-mers.
Auteurs : Yaron Orenstein [Israël]Source :
- Journal of computational biology : a journal of computational molecular cell biology [ 1557-8666 ] ; 2020.
Abstract
Peptide arrays measure the binding intensity of a specific protein to thousands of amino acid peptides. By using peptides that cover all k-mers, a comprehensive picture of the binding spectrum is obtained. Researchers would like to measure binding to the longest k-mer possible but are constrained by the number of peptides that can fit into a single microarray. A key challenge is designing a minimum number of peptides that cover all k-mers. Here, we suggest a novel idea to reduce the length of the sequence covering all k-mers by utilizing a unique property of the peptide synthesis process. Since the synthesis can start from both ends of the peptide template, it is enough to cover each k-mer or its reverse and to use the same template twice: in forward and reverse. Then, the computational problem is to generate a minimum length sequence that for each k-mer either contains the k-mer or its reverse. In this study, we present a new algorithm, called ReverseCAKE, to generate such a sequence. ReverseCAKE runs in time linear in the output size and is guaranteed to produce a sequence that is longer by at mostΘ ( n log n ) characters compared with the optimum n. The obtained saving factor by ReverseCAKE approaches the theoretical lower bound as k increases. In addition, we formulated the problem as an integer linear program and empirically observed that the solutions obtained by ReverseCAKE are near-optimal. Through this work, we enable more effective design of peptide microarrays.
DOI: 10.1089/cmb.2019.0448
PubMed: 31995404
Links toward previous steps (curation, corpus...)
- to stream PubMed, to step Corpus: 000269
- to stream PubMed, to step Curation: 000269
- to stream PubMed, to step Checkpoint: 000094
Links to Exploration step
pubmed:31995404Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Reverse de Bruijn: Utilizing Reverse Peptide Synthesis to Cover All Amino Acid <i>k</i>
-mers.</title>
<author><name sortKey="Orenstein, Yaron" sort="Orenstein, Yaron" uniqKey="Orenstein Y" first="Yaron" last="Orenstein">Yaron Orenstein</name>
<affiliation wicri:level="1"><nlm:affiliation>School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva, Israel.</nlm:affiliation>
<country xml:lang="fr">Israël</country>
<wicri:regionArea>School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva</wicri:regionArea>
<wicri:noRegion>Beer-Sheva</wicri:noRegion>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">PubMed</idno>
<date when="2020">2020</date>
<idno type="RBID">pubmed:31995404</idno>
<idno type="pmid">31995404</idno>
<idno type="doi">10.1089/cmb.2019.0448</idno>
<idno type="wicri:Area/PubMed/Corpus">000269</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">000269</idno>
<idno type="wicri:Area/PubMed/Curation">000269</idno>
<idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">000269</idno>
<idno type="wicri:Area/PubMed/Checkpoint">000094</idno>
<idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">000094</idno>
<idno type="wicri:Area/Ncbi/Merge">002499</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en">Reverse de Bruijn: Utilizing Reverse Peptide Synthesis to Cover All Amino Acid <i>k</i>
-mers.</title>
<author><name sortKey="Orenstein, Yaron" sort="Orenstein, Yaron" uniqKey="Orenstein Y" first="Yaron" last="Orenstein">Yaron Orenstein</name>
<affiliation wicri:level="1"><nlm:affiliation>School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva, Israel.</nlm:affiliation>
<country xml:lang="fr">Israël</country>
<wicri:regionArea>School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva</wicri:regionArea>
<wicri:noRegion>Beer-Sheva</wicri:noRegion>
</affiliation>
</author>
</analytic>
<series><title level="j">Journal of computational biology : a journal of computational molecular cell biology</title>
<idno type="eISSN">1557-8666</idno>
<imprint><date when="2020" type="published">2020</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
</fileDesc>
<profileDesc><textClass></textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en"><b>Peptide arrays measure the binding intensity of a specific protein to thousands of amino acid peptides. By using peptides that cover all <i>k</i>
-mers, a comprehensive picture of the binding spectrum is obtained. Researchers would like to measure binding to the longest <i>k</i>
-mer possible but are constrained by the number of peptides that can fit into a single microarray. A key challenge is designing a minimum number of peptides that cover all <i>k</i>
-mers. Here, we suggest a novel idea to reduce the length of the sequence covering all <i>k</i>
-mers by utilizing a unique property of the peptide synthesis process. Since the synthesis can start from both ends of the peptide template, it is enough to cover each <i>k</i>
-mer or its reverse and to use the same template twice: in forward and reverse. Then, the computational problem is to generate a minimum length sequence that for each <i>k</i>
-mer either contains the <i>k</i>
-mer or its reverse. In this study, we present a new algorithm, called ReverseCAKE, to generate such a sequence. ReverseCAKE runs in time linear in the output size and is guaranteed to produce a sequence that is longer by at most</b>
<mml:math><mml:mi>Θ</mml:mi>
<mml:mrow><mml:mo>(</mml:mo>
<mml:mrow><mml:msqrt><mml:mrow><mml:mi>n</mml:mi>
</mml:mrow>
</mml:msqrt>
<mml:mo>log</mml:mo>
<mml:mi>n</mml:mi>
</mml:mrow>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:math>
<b>characters compared with the optimum <i>n</i>
. The obtained saving factor by ReverseCAKE approaches the theoretical lower bound as <i>k</i>
increases. In addition, we formulated the problem as an integer linear program and empirically observed that the solutions obtained by ReverseCAKE are near-optimal. Through this work, we enable more effective design of peptide microarrays.</b>
</div>
</front>
</TEI>
<pubmed><MedlineCitation Status="In-Data-Review" Owner="NLM"><PMID Version="1">31995404</PMID>
<DateRevised><Year>2020</Year>
<Month>03</Month>
<Day>12</Day>
</DateRevised>
<Article PubModel="Print-Electronic"><Journal><ISSN IssnType="Electronic">1557-8666</ISSN>
<JournalIssue CitedMedium="Internet"><Volume>27</Volume>
<Issue>3</Issue>
<PubDate><Year>2020</Year>
<Month>Mar</Month>
</PubDate>
</JournalIssue>
<Title>Journal of computational biology : a journal of computational molecular cell biology</Title>
<ISOAbbreviation>J. Comput. Biol.</ISOAbbreviation>
</Journal>
<ArticleTitle>Reverse de Bruijn: Utilizing Reverse Peptide Synthesis to Cover All Amino Acid <i>k</i>
-mers.</ArticleTitle>
<Pagination><MedlinePgn>376-385</MedlinePgn>
</Pagination>
<ELocationID EIdType="doi" ValidYN="Y">10.1089/cmb.2019.0448</ELocationID>
<Abstract><AbstractText><b>Peptide arrays measure the binding intensity of a specific protein to thousands of amino acid peptides. By using peptides that cover all <i>k</i>
-mers, a comprehensive picture of the binding spectrum is obtained. Researchers would like to measure binding to the longest <i>k</i>
-mer possible but are constrained by the number of peptides that can fit into a single microarray. A key challenge is designing a minimum number of peptides that cover all <i>k</i>
-mers. Here, we suggest a novel idea to reduce the length of the sequence covering all <i>k</i>
-mers by utilizing a unique property of the peptide synthesis process. Since the synthesis can start from both ends of the peptide template, it is enough to cover each <i>k</i>
-mer or its reverse and to use the same template twice: in forward and reverse. Then, the computational problem is to generate a minimum length sequence that for each <i>k</i>
-mer either contains the <i>k</i>
-mer or its reverse. In this study, we present a new algorithm, called ReverseCAKE, to generate such a sequence. ReverseCAKE runs in time linear in the output size and is guaranteed to produce a sequence that is longer by at most</b>
<mml:math><mml:mi>Θ</mml:mi>
<mml:mrow><mml:mo>(</mml:mo>
<mml:mrow><mml:msqrt><mml:mrow><mml:mi>n</mml:mi>
</mml:mrow>
</mml:msqrt>
<mml:mo>log</mml:mo>
<mml:mi>n</mml:mi>
</mml:mrow>
<mml:mo>)</mml:mo>
</mml:mrow>
</mml:math>
<b>characters compared with the optimum <i>n</i>
. The obtained saving factor by ReverseCAKE approaches the theoretical lower bound as <i>k</i>
increases. In addition, we formulated the problem as an integer linear program and empirically observed that the solutions obtained by ReverseCAKE are near-optimal. Through this work, we enable more effective design of peptide microarrays.</b>
</AbstractText>
</Abstract>
<AuthorList CompleteYN="Y"><Author ValidYN="Y"><LastName>Orenstein</LastName>
<ForeName>Yaron</ForeName>
<Initials>Y</Initials>
<AffiliationInfo><Affiliation>School of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer-Sheva, Israel.</Affiliation>
</AffiliationInfo>
</Author>
</AuthorList>
<Language>eng</Language>
<PublicationTypeList><PublicationType UI="D016428">Journal Article</PublicationType>
</PublicationTypeList>
<ArticleDate DateType="Electronic"><Year>2020</Year>
<Month>01</Month>
<Day>29</Day>
</ArticleDate>
</Article>
<MedlineJournalInfo><Country>United States</Country>
<MedlineTA>J Comput Biol</MedlineTA>
<NlmUniqueID>9433358</NlmUniqueID>
<ISSNLinking>1066-5277</ISSNLinking>
</MedlineJournalInfo>
<CitationSubset>IM</CitationSubset>
<KeywordList Owner="NOTNLM"><Keyword MajorTopicYN="N">array design</Keyword>
<Keyword MajorTopicYN="N">de Bruijn graph</Keyword>
<Keyword MajorTopicYN="N">de Bruijn sequence</Keyword>
<Keyword MajorTopicYN="N">peptide array</Keyword>
<Keyword MajorTopicYN="N">reverse synthesis</Keyword>
</KeywordList>
</MedlineCitation>
<PubmedData><History><PubMedPubDate PubStatus="pubmed"><Year>2020</Year>
<Month>1</Month>
<Day>30</Day>
<Hour>6</Hour>
<Minute>0</Minute>
</PubMedPubDate>
<PubMedPubDate PubStatus="medline"><Year>2020</Year>
<Month>1</Month>
<Day>30</Day>
<Hour>6</Hour>
<Minute>0</Minute>
</PubMedPubDate>
<PubMedPubDate PubStatus="entrez"><Year>2020</Year>
<Month>1</Month>
<Day>30</Day>
<Hour>6</Hour>
<Minute>0</Minute>
</PubMedPubDate>
</History>
<PublicationStatus>ppublish</PublicationStatus>
<ArticleIdList><ArticleId IdType="pubmed">31995404</ArticleId>
<ArticleId IdType="doi">10.1089/cmb.2019.0448</ArticleId>
</ArticleIdList>
</PubmedData>
</pubmed>
<affiliations><list><country><li>Israël</li>
</country>
</list>
<tree><country name="Israël"><noRegion><name sortKey="Orenstein, Yaron" sort="Orenstein, Yaron" uniqKey="Orenstein Y" first="Yaron" last="Orenstein">Yaron Orenstein</name>
</noRegion>
</country>
</tree>
</affiliations>
</record>
Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Ncbi/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002499 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd -nk 002499 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien |wiki= Sante |area= MersV1 |flux= Ncbi |étape= Merge |type= RBID |clé= pubmed:31995404 |texte= Reverse de Bruijn: Utilizing Reverse Peptide Synthesis to Cover All Amino Acid k-mers. }}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/RBID.i -Sk "pubmed:31995404" \ | HfdSelect -Kh $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd \ | NlmPubMed2Wicri -a MersV1
![]() | This area was generated with Dilib version V0.6.33. | ![]() |