首页    期刊浏览 2024年11月08日 星期五
登录注册

文章基本信息

  • 标题:On the Complexity of Positional Sequencing by Hybridization
  • 本地全文:下载
  • 作者:Amir Ben-Dor ; Itsik Peer ; Roded Sharan
  • 期刊名称:Electronic Colloquium on Computational Complexity
  • 印刷版ISSN:1433-8092
  • 出版年度:2001
  • 卷号:2001
  • 出版社:Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
  • 摘要:In sequencing by hybridization (SBH), one has to reconstruct a sequence from its l -long substrings. SBH was proposed as an alternative to gel-based DNA sequencing approaches, but in its original form the method is not competitive. Positional SBH (PSBH) is a recently proposed enhancement of SBH in which one has additional information about the possible positions of each substring along the target sequence. We give a linear time algorithm for solving PSBH when each substring has at most two possible positions. On the other hand, we prove that the problem is NP-complete if each substring has at most three possible positions. We also show that PSBH is NP-complete if the set of allowed positions for each substring is an interval of length k , and provide a fast algorithm for the latter problem when k is bounded.
国家哲学社会科学文献中心版权所有