Computational complexity of isothermic DNA sequencing by hybridization

被引：11

作者：

Blazewicz, J ^{[1
]}

Kasprzak, M

机构：

[1] Poznan Univ Technol, Inst Comp Sci, Poznan, Poland

[2] Polish Acad Sci, Inst Bioorgan Chem, Poznan, Poland

来源：

DISCRETE APPLIED MATHEMATICS | 2006年 / 154卷 / 05期

关键词：

DNA sequencing; computational complexity; eulerian path;

D O I：

10.1016/j.dam.2005.05.028

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

In the paper, the computational complexity of several variants of the problem of isothermic DNA sequencing by hybridization, is analyzed. The isothermic sequencing is a recent method, in which isothermic oligonucleotide libraries are used during the hybridization with an unknown DNA fragment. The variants of the isothermic DNA sequencing problem with errors in the hybridization data, negative ones or positive ones, are proved to be strongly NP-hard. On the other hand, the polynomial time algorithm for the ideal case with no errors is proposed. (c) 2005 Elsevier B.V. All rights reserved.

引用

页码：718 / 729

页数：12

共 34 条

[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] Euler circuits and DNA sequencing by hybridization
Arratia, R
Bollobás, B
Coppersmith, D
Sorkin, GB
[J]. DISCRETE APPLIED MATHEMATICS, 2000, 104 (1-3) : 63 - 96
[5] A NOVEL METHOD FOR NUCLEIC-ACID SEQUENCE DETERMINATION
BAINS, W
SMITH, GC
[J]. JOURNAL OF THEORETICAL BIOLOGY, 1988, 135 (03) : 303 - 307
[6] Bang-Jensen J., 2001, DIGRAPHS THEORY ALGO
[7] On the complexity of positional sequencing by hybridization
Ben-Dor, A
Pe'er, I
Shamir, R
Sharan, R
[J]. JOURNAL OF COMPUTATIONAL BIOLOGY, 2001, 8 (04) : 361 - 371
[8] Sequencing by hybridization with isothermic oligonucleotide libraries
Blazewicz, J
Formanowicz, P
Kasprzak, M
Markiewicz, WT
[J]. DISCRETE APPLIED MATHEMATICS, 2004, 145 (01) : 40 - 51
[9] On some properties of DNA graphs
Blazewicz, J
Hertz, A
Kobler, D
de Werra, D
[J]. DISCRETE APPLIED MATHEMATICS, 1999, 98 (1-2) : 1 - 19
[10] Complexity of DNA sequencing by hybridization
Blazewicz, J
Kasprzak, M
[J]. THEORETICAL COMPUTER SCIENCE, 2003, 290 (03) : 1459 - 1473

← 1 2 3 4 →