File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Deterministic polynomial-time algorithms for designing short DNA words

TitleDeterministic polynomial-time algorithms for designing short DNA words
Authors
Keywordscoding theory
derandomization
DNA computating
DNA words design
expander codes
Ramanujan graphs
Issue Date2010
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
The 7th Annual Conference on Theory and Applications of Models of Computation (TAMC 2010), Prague, Czech Republic, 7-11 June 2010. In Lecture Notes in Computer Science, 2010, v. 6108, p. 308-319 How to Cite?
AbstractDesigning short DNA words is a problem of constructing n DNA strings (words) with the minimum length such that the Hamming distance between each pair is at least k and the words satisfy a set of extra constraints. This problem has applications in DNA computing, DNA self-assembly, and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code size for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi and Schweller developed polynomial-time randomized algorithms to construct n DNA words of length 9· max {logn,k} satisfying a sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on expander codes, Ramanujan graphs, and derandomization techniques. Our algorithms can construct n DNA words of length max {3logn, 4k} or 2.1 logn + 6.28 k satisfying the same sets of constraints as the words constructed by the algorithms of Kao et al. We have also extended these algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work. © 2010 Springer-Verlag.
DescriptionLNCS v. 6108 is Proceedings of the 7th Annual Conference, TAMC 2010
Persistent Identifierhttp://hdl.handle.net/10722/93415
ISSN
2023 SCImago Journal Rankings: 0.606
References

 

DC FieldValueLanguage
dc.contributor.authorKao, MYen_HK
dc.contributor.authorLeung, HCMen_HK
dc.contributor.authorSun, Hen_HK
dc.contributor.authorZhang, Yen_HK
dc.date.accessioned2010-09-25T15:00:28Z-
dc.date.available2010-09-25T15:00:28Z-
dc.date.issued2010en_HK
dc.identifier.citationThe 7th Annual Conference on Theory and Applications of Models of Computation (TAMC 2010), Prague, Czech Republic, 7-11 June 2010. In Lecture Notes in Computer Science, 2010, v. 6108, p. 308-319en_HK
dc.identifier.issn0302-9743en_HK
dc.identifier.urihttp://hdl.handle.net/10722/93415-
dc.descriptionLNCS v. 6108 is Proceedings of the 7th Annual Conference, TAMC 2010-
dc.description.abstractDesigning short DNA words is a problem of constructing n DNA strings (words) with the minimum length such that the Hamming distance between each pair is at least k and the words satisfy a set of extra constraints. This problem has applications in DNA computing, DNA self-assembly, and DNA arrays. Previous works include those that extended results from coding theory to obtain bounds on code size for biologically motivated constraints and those that applied heuristic local searches, genetic algorithms, and randomized algorithms. In particular, Kao, Sanghi and Schweller developed polynomial-time randomized algorithms to construct n DNA words of length 9· max {logn,k} satisfying a sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithms to construct DNA words based on expander codes, Ramanujan graphs, and derandomization techniques. Our algorithms can construct n DNA words of length max {3logn, 4k} or 2.1 logn + 6.28 k satisfying the same sets of constraints as the words constructed by the algorithms of Kao et al. We have also extended these algorithms to construct words that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work. © 2010 Springer-Verlag.en_HK
dc.languageengen_HK
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_HK
dc.relation.ispartofLecture Notes in Computer Scienceen_HK
dc.rightsThe original publication is available at www.springerlink.com-
dc.subjectcoding theoryen_HK
dc.subjectderandomizationen_HK
dc.subjectDNA computatingen_HK
dc.subjectDNA words designen_HK
dc.subjectexpander codesen_HK
dc.subjectRamanujan graphsen_HK
dc.titleDeterministic polynomial-time algorithms for designing short DNA wordsen_HK
dc.typeConference_Paperen_HK
dc.identifier.emailLeung, HCM:cmleung2@cs.hku.hken_HK
dc.identifier.authorityLeung, HCM=rp00144en_HK
dc.description.naturelink_to_subscribed_fulltext-
dc.identifier.doi10.1007/978-3-642-13562-0_28en_HK
dc.identifier.scopuseid_2-s2.0-77954437447en_HK
dc.identifier.hkuros169726en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-77954437447&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume6108 LNCSen_HK
dc.identifier.spage308en_HK
dc.identifier.epage319en_HK
dc.publisher.placeGermanyen_HK
dc.description.otherThe 7th Annual Conference on Theory and Applications of Models of Computation (TAMC 2010), Prague, Czech Republic, 7-11 June 2010. In Lecture Notes in Computer Science, 2010, v. 6108, p. 308-319-
dc.identifier.scopusauthoridKao, MY=7202198147en_HK
dc.identifier.scopusauthoridLeung, HCM=35233742700en_HK
dc.identifier.scopusauthoridSun, H=14619833800en_HK
dc.identifier.scopusauthoridZhang, Y=7601319872en_HK
dc.identifier.issnl0302-9743-

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats