File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
 Publisher Website: 10.1007/9783642135620_28
 Scopus: eid_2s2.077954437447
 Find via
Supplementary

Citations:
 Scopus: 0
 Appears in Collections:
Conference Paper: Deterministic polynomialtime algorithms for designing short DNA words
Title  Deterministic polynomialtime algorithms for designing short DNA words 

Authors  
Keywords  coding theory derandomization DNA computating DNA words design expander codes Ramanujan graphs 
Issue Date  2010 
Publisher  Springer 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, 711 June 2010. In Lecture Notes in Computer Science, 2010, v. 6108, p. 308319 How to Cite? 
Abstract  Designing 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 selfassembly, 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 polynomialtime 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 polynomialtime 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 SpringerVerlag. 
Description  LNCS v. 6108 is Proceedings of the 7th Annual Conference, TAMC 2010 
Persistent Identifier  http://hdl.handle.net/10722/93415 
ISSN  2005 Impact Factor: 0.402 2015 SCImago Journal Rankings: 0.252 
References 
DC Field  Value  Language 

dc.contributor.author  Kao, MY  en_HK 
dc.contributor.author  Leung, HCM  en_HK 
dc.contributor.author  Sun, H  en_HK 
dc.contributor.author  Zhang, Y  en_HK 
dc.date.accessioned  20100925T15:00:28Z   
dc.date.available  20100925T15:00:28Z   
dc.date.issued  2010  en_HK 
dc.identifier.citation  The 7th Annual Conference on Theory and Applications of Models of Computation (TAMC 2010), Prague, Czech Republic, 711 June 2010. In Lecture Notes in Computer Science, 2010, v. 6108, p. 308319  en_HK 
dc.identifier.issn  03029743  en_HK 
dc.identifier.uri  http://hdl.handle.net/10722/93415   
dc.description  LNCS v. 6108 is Proceedings of the 7th Annual Conference, TAMC 2010   
dc.description.abstract  Designing 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 selfassembly, 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 polynomialtime 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 polynomialtime 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 SpringerVerlag.  en_HK 
dc.language  eng  en_HK 
dc.publisher  Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/  en_HK 
dc.relation.ispartof  Lecture Notes in Computer Science  en_HK 
dc.rights  The original publication is available at www.springerlink.com   
dc.subject  coding theory  en_HK 
dc.subject  derandomization  en_HK 
dc.subject  DNA computating  en_HK 
dc.subject  DNA words design  en_HK 
dc.subject  expander codes  en_HK 
dc.subject  Ramanujan graphs  en_HK 
dc.title  Deterministic polynomialtime algorithms for designing short DNA words  en_HK 
dc.type  Conference_Paper  en_HK 
dc.identifier.email  Leung, HCM:cmleung2@cs.hku.hk  en_HK 
dc.identifier.authority  Leung, HCM=rp00144  en_HK 
dc.description.nature  link_to_subscribed_fulltext   
dc.identifier.doi  10.1007/9783642135620_28  en_HK 
dc.identifier.scopus  eid_2s2.077954437447  en_HK 
dc.identifier.hkuros  169726  en_HK 
dc.relation.references  http://www.scopus.com/mlt/select.url?eid=2s2.077954437447&selection=ref&src=s&origin=recordpage  en_HK 
dc.identifier.volume  6108 LNCS  en_HK 
dc.identifier.spage  308  en_HK 
dc.identifier.epage  319  en_HK 
dc.publisher.place  Germany  en_HK 
dc.description.other  The 7th Annual Conference on Theory and Applications of Models of Computation (TAMC 2010), Prague, Czech Republic, 711 June 2010. In Lecture Notes in Computer Science, 2010, v. 6108, p. 308319   
dc.identifier.scopusauthorid  Kao, MY=7202198147  en_HK 
dc.identifier.scopusauthorid  Leung, HCM=35233742700  en_HK 
dc.identifier.scopusauthorid  Sun, H=14619833800  en_HK 
dc.identifier.scopusauthorid  Zhang, Y=7601319872  en_HK 