Complexity of DNA sequencing by hybridization

被引：39

作者：

Blazewicz, J

Kasprzak, M

机构：

[1] Polish Acad Sci, Inst Bioorgan Chem, PL-61704 Poznan, Poland

[2] Poznan Univ Tech, Inst Comp Sci, PL-60965 Poznan, Poland

来源：

THEORETICAL COMPUTER SCIENCE | 2003年 / 290卷 / 03期

关键词：

DNA sequencing; computational complexity; computational biology;

D O I：

10.1016/S0304-3975(02)00063-4

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

In the paper, the question of the complexity of the combinatorial part of the DNA sequencing by hybridization, is analyzed. Subproblems of the general problem, depending on the type of error (positive, negative), are distinguished. Since decision versions of the subproblems assuming only one type of error are trivial, complexities of the search counterparts are studied. Both search subproblems are proved to be strongly NP-hard, as well as their uniquely promised versions. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：1459 / 1473

页数：15

共 19 条

[1]

[Anonymous], [No title captured], Patent No. 8810400

[2]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[3]

APOSTOLICO A, 1997, AM MATH SOC DIMACS S

[4] On some properties of DNA graphs [J].