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

DOI

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 
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
@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},
     year = {2005},
     publisher = {EDP-Sciences},
     volume = {39},
     number = {4},
     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

Cité par Sources :