File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1016/j.tcs.2012.12.030
- Scopus: eid_2-s2.0-84879080194
- WOS: WOS:000321422500014
- Find via
Supplementary
- Citations:
- Appears in Collections:
Article: Deterministic Polynomial-Time Algorithms for Designing Short DNA Words
Title | Deterministic Polynomial-Time Algorithms for Designing Short DNA Words |
---|---|
Authors | |
Keywords | DNA word design Deterministic algorithms Derandomization |
Issue Date | 2013 |
Publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs |
Citation | Theoretical Computer Science, 2013, v. 494, p. 144-160 How to Cite? |
Abstract | Designing short DNA words is a problem of constructing a set (i.e., code) of n DNA strings (i.e., words) with the minimum length such that the Hamming distance between each pair of words is at least k and the n words satisfy a set of additional constraints. This problem has applications in, e.g., DNA self-assembly and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code and word sizes for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi, and Schweller [16] developed polynomial-time randomized algorithms to construct n DNA words of length within a multiplicative constant of the smallest possible word length (e.g., 9×max{logn,k}) that satisfy various sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on derandomization techniques. Our algorithms can construct n DNA words of shorter length (e.g., 2.1logn+6.28k) and can satisfy the same sets of constraints as the words constructed by the algorithms of Kao et al. Furthermore, we extend these new algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work. |
Persistent Identifier | http://hdl.handle.net/10722/185124 |
ISSN | 2023 Impact Factor: 0.9 2023 SCImago Journal Rankings: 0.570 |
ISI Accession Number ID |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kao, MY | - |
dc.contributor.author | Leung, HCM | - |
dc.contributor.author | Sun, H | - |
dc.contributor.author | Zhang, Y | - |
dc.date.accessioned | 2013-07-15T10:32:20Z | - |
dc.date.available | 2013-07-15T10:32:20Z | - |
dc.date.issued | 2013 | - |
dc.identifier.citation | Theoretical Computer Science, 2013, v. 494, p. 144-160 | - |
dc.identifier.issn | 0304-3975 | - |
dc.identifier.uri | http://hdl.handle.net/10722/185124 | - |
dc.description.abstract | Designing short DNA words is a problem of constructing a set (i.e., code) of n DNA strings (i.e., words) with the minimum length such that the Hamming distance between each pair of words is at least k and the n words satisfy a set of additional constraints. This problem has applications in, e.g., DNA self-assembly and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code and word sizes for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi, and Schweller [16] developed polynomial-time randomized algorithms to construct n DNA words of length within a multiplicative constant of the smallest possible word length (e.g., 9×max{logn,k}) that satisfy various sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on derandomization techniques. Our algorithms can construct n DNA words of shorter length (e.g., 2.1logn+6.28k) and can satisfy the same sets of constraints as the words constructed by the algorithms of Kao et al. Furthermore, we extend these new algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work. | - |
dc.language | eng | - |
dc.publisher | Elsevier BV. The Journal's web site is located at http://www.elsevier.com/locate/tcs | - |
dc.relation.ispartof | Theoretical Computer Science | - |
dc.subject | DNA word design | - |
dc.subject | Deterministic algorithms | - |
dc.subject | Derandomization | - |
dc.title | Deterministic Polynomial-Time Algorithms for Designing Short DNA Words | - |
dc.type | Article | - |
dc.identifier.email | Leung, HCM: cmleung2@cs.hku.hk | - |
dc.identifier.email | Zhang, Y: yongzh@hkucc.hku.hk | - |
dc.identifier.authority | Leung, HCM=rp00144 | - |
dc.description.nature | link_to_OA_fulltext | - |
dc.identifier.doi | 10.1016/j.tcs.2012.12.030 | - |
dc.identifier.scopus | eid_2-s2.0-84879080194 | - |
dc.identifier.hkuros | 215787 | - |
dc.identifier.volume | 494 | - |
dc.identifier.spage | 144 | - |
dc.identifier.epage | 160 | - |
dc.identifier.isi | WOS:000321422500014 | - |
dc.publisher.place | Netherlands | - |
dc.identifier.issnl | 0304-3975 | - |