Algorithms for testing that sets of DNA words concatenate without secondary structure

Mirela Andronescu; Danielle Dees; Laura Slaybaugh; Yinglei Zhao; Anne Condon; Barry Cohen; Steven Skiena

doi:10.1023/B:NACO.0000006770.91995.ec

Algorithms for testing that sets of DNA words concatenate without secondary structure

Mirela Andronescu
, Danielle Dees
, Laura Slaybaugh
, Yinglei Zhao
, Anne Condon
, Barry Cohen
, Steven Skiena

Computer Science

University of British Columbia
Georgia Institute of Technology
Rose Hulman Institute Technology
Stony Brook University

Research output: Contribution to journal › Article › peer-review

5 Scopus citations

Abstract

We present an efficient algorithm for determining whether all molecules in a combinatorial set of DNA or RNA strands are structure free, and thus available for bonding to their Watson-Crick complements. This work is motivated by the goal of testing whether strands used in DNA computations or as molecular bar-codes are structure free, where the strands are concatenations of short words. We also present an algorithm for determining whether all words in S*, for some finite set S of equi-length words, are structure free.

Original language	English
Pages (from-to)	391-415
Number of pages	25
Journal	Natural Computing
Volume	2
Issue number	4
DOIs	https://doi.org/10.1023/B:NACO.0000006770.91995.ec
State	Published - 2003

Keywords

RNA secondary structure
Testing DNA word sets

Access to Document

10.1023/B:NACO.0000006770.91995.ec

Cite this

@article{29a8db3a76fa4adabde23f99a9641a4c,

title = "Algorithms for testing that sets of DNA words concatenate without secondary structure",

abstract = "We present an efficient algorithm for determining whether all molecules in a combinatorial set of DNA or RNA strands are structure free, and thus available for bonding to their Watson-Crick complements. This work is motivated by the goal of testing whether strands used in DNA computations or as molecular bar-codes are structure free, where the strands are concatenations of short words. We also present an algorithm for determining whether all words in S*, for some finite set S of equi-length words, are structure free.",

keywords = "RNA secondary structure, Testing DNA word sets",

author = "Mirela Andronescu and Danielle Dees and Laura Slaybaugh and Yinglei Zhao and Anne Condon and Barry Cohen and Steven Skiena",

year = "2003",

doi = "10.1023/B:NACO.0000006770.91995.ec",

language = "English",

volume = "2",

pages = "391--415",

journal = "Natural Computing",

issn = "1567-7818",

number = "4",

}

TY - JOUR

T1 - Algorithms for testing that sets of DNA words concatenate without secondary structure

AU - Andronescu, Mirela

AU - Dees, Danielle

AU - Slaybaugh, Laura

AU - Zhao, Yinglei

AU - Condon, Anne

AU - Cohen, Barry

AU - Skiena, Steven

PY - 2003

Y1 - 2003

N2 - We present an efficient algorithm for determining whether all molecules in a combinatorial set of DNA or RNA strands are structure free, and thus available for bonding to their Watson-Crick complements. This work is motivated by the goal of testing whether strands used in DNA computations or as molecular bar-codes are structure free, where the strands are concatenations of short words. We also present an algorithm for determining whether all words in S*, for some finite set S of equi-length words, are structure free.

AB - We present an efficient algorithm for determining whether all molecules in a combinatorial set of DNA or RNA strands are structure free, and thus available for bonding to their Watson-Crick complements. This work is motivated by the goal of testing whether strands used in DNA computations or as molecular bar-codes are structure free, where the strands are concatenations of short words. We also present an algorithm for determining whether all words in S*, for some finite set S of equi-length words, are structure free.

KW - RNA secondary structure

KW - Testing DNA word sets

UR - https://www.scopus.com/pages/publications/4344591854

U2 - 10.1023/B:NACO.0000006770.91995.ec

DO - 10.1023/B:NACO.0000006770.91995.ec

M3 - Article

AN - SCOPUS:4344591854

SN - 1567-7818

VL - 2

SP - 391

EP - 415

JO - Natural Computing

JF - Natural Computing

IS - 4

ER -

Algorithms for testing that sets of DNA words concatenate without secondary structure

Abstract

Keywords

Access to Document

Other files and links

Fingerprint

Cite this