• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Theory and application of models of computation >Deterministic Polynomial-Time Algorithms for Designing Short DNA Words
【24h】

Deterministic Polynomial-Time Algorithms for Designing Short DNA Words

机译：设计短DNA词的确定性多项式时间算法

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

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 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{3 log n, 4k} or 2.1 log n + 6.28k 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.
机译：设计短的DNA单词是构造n个具有最小长度的DNA字符串（单词）的问题，以使每对之间的汉明距离至少为k，并且单词满足一组额外的约束。此问题已应用于DNA计算，DNA自组装和DNA阵列。先前的工作包括那些扩展了编码理论的结果以获得生物学动机约束的代码大小界限的应用，以及那些应用启发式局部搜索，遗传算法和随机算法的应用。特别是，Kao，Sanghi和Schweller开发了多项式时间随机算法来构造长度为9·max {logn，k}的n个DNA单词，这些单词具有很高的概率来满足一组约束。在本文中，我们给出确定性多项式时间算法，以基于扩展器代码，Ramanujan图和去随机化技术构造DNA单词。我们的算法可以构建n个长度为max {3 log n，4k}或2.1 log n + 6.28k的DNA单词，满足与Kao等人算法构建的单词相同的约束集。我们还扩展了这些算法，以构造满足Kao等人的算法满足更大约束集的单词。不工作。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号