Geodesic
Combinatorial optimization in DNA mapping - A computational thread of the simplified partial digest problem
RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 4, pp. 227-241

Voir la notice de l'article provenant de la source Numdam

In the paper, the problem of the genome mapping of DNA molecules, is presented. In particular, the new approach - the Simplified Partial Digest Problem (SPDP), is analyzed. This approach, although easy in laboratory implementation and robust with respect to measurement errors, when formulated in terms of a combinatorial search problem, is proved to be strongly NP-hard for the general error-free case. For a subproblem of the SPDP, a simple O(n log n)-time algorithm is given, where n is a number of restriction sites.

DOI : 10.1051/ro:2006007
Keywords: combinatorial optimization, DNA restriction mapping, partial digest, computational complexity 
@article{RO_2005__39_4_227_0,
     author = {Blazewicz, Jacek and Kasprzak, Marta},
     title = {Combinatorial optimization in {DNA} mapping - {A} computational thread of the simplified partial digest problem},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {227--241},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {4},
     year = {2005},
     doi = {10.1051/ro:2006007},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ro:2006007/}
}
TY  - JOUR
AU  - Blazewicz, Jacek
AU  - Kasprzak, Marta
TI  - Combinatorial optimization in DNA mapping - A computational thread of the simplified partial digest problem
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2005
SP  - 227
EP  - 241
VL  - 39
IS  - 4
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ro:2006007/
DO  - 10.1051/ro:2006007
LA  - en
ID  - RO_2005__39_4_227_0
ER  - 
%0 Journal Article
%A Blazewicz, Jacek
%A Kasprzak, Marta
%T Combinatorial optimization in DNA mapping - A computational thread of the simplified partial digest problem
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2005
%P 227-241
%V 39
%N 4
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ro:2006007/
%R 10.1051/ro:2006007
%G en
%F RO_2005__39_4_227_0
Blazewicz, Jacek; Kasprzak, Marta. Combinatorial optimization in DNA mapping - A computational thread of the simplified partial digest problem. RAIRO - Operations Research - Recherche Opérationnelle, Tome 39 (2005) no. 4, pp. 227-241. doi: 10.1051/ro:2006007

Cité par Sources :