Deterministic polynomial-time algorithms for designing short DNA words
文献类型：期刊论文
| 作者 | Kao, Ming-Yang; Leung, Henry C. M.; Sun, He; Zhang, Yong |
| 刊名 | THEORETICAL COMPUTER SCIENCE
 |
| 出版日期 | 2013 |
| 英文摘要 | 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{log n, k}) that satisfy various sets of constraints with high probability. In this paper, we give deterministic polynomial-time algorithmsto construct DNA words based on derandomization techniques. Our algorithms can construct n DNA words of shorter length (e.g., 2.1 log n + 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 constructwords that satisfy a larger set of constraints for which the algorithms of Kao et al. do not work. (c) 2013 Elsevier B.V. All rights reserved. |
| 收录类别 | SCI |
| 原文出处 | http://www.sciencedirect.com/science/article/pii/S0304397512011450 |
| 语种 | 英语 |
| 源URL | [http://ir.siat.ac.cn:8080/handle/172644/5037]  |
| 专题 | 深圳先进技术研究院_数字所 |
| 作者单位 | THEORETICAL COMPUTER SCIENCE |
| 推荐引用方式 GB/T 7714 | Kao, Ming-Yang,Leung, Henry C. M.,Sun, He,et al. Deterministic polynomial-time algorithms for designing short DNA words[J]. THEORETICAL COMPUTER SCIENCE,2013. |
| APA | Kao, Ming-Yang,Leung, Henry C. M.,Sun, He,&Zhang, Yong.(2013).Deterministic polynomial-time algorithms for designing short DNA words.THEORETICAL COMPUTER SCIENCE. |
| MLA | Kao, Ming-Yang,et al."Deterministic polynomial-time algorithms for designing short DNA words".THEORETICAL COMPUTER SCIENCE (2013). |
入库方式： OAI收割
来源：深圳先进技术研究院
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。