EUDML

The search session has expired. Please query the service again.

Currently displaying 1 – 2 of 2

Order by Relevance | Title | Year of publication

Combinatorial optimization in DNA mapping — A computational thread of the simplified partial digest problem

Jacek Blazewicz; Marta Kasprzak — 2005

RAIRO - Operations Research - Recherche Opérationnelle

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...

Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem

Jacek Blazewicz; Marta Kasprzak — 2006

RAIRO - Operations Research

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(log)-time algorithm is given, where is a number of restriction...

Page 1

Download Results (CSV)

Advanced Search

Formula preview

Currently displaying 1 – 2 of 2

Combinatorial optimization in DNA mapping — A computational thread of the simplified partial digest problem

Combinatorial optimization in DNA mapping — a computational thread of the Simplified Partial Digest Problem