Seminario: The Partial Digest Problem – An Intriguing Challenge in Computational Biology

Mark Cieliebak
ETH, Zurich, Suiza

12 de Marzo, 11:30 am
Auditorio DCC
Blanco Encalada 2120, tercer piso

Abstract

In the Partial Digest problem we are given a multiset of integers and we ask for a set of points on a line such that the pairwise distances of the points form the given multiset. This problem is one of the most intriguing problems from computational biology: on the one hand, it is a basic problem in DNA sequencing, namely physical DNA mapping; on the other hand, its computational complexity is a long-standing open problem. In fact, neither a polynomial time algorithm nor a proof of NP-hardness is known.

In this talk we give a survey of the Partial Digest problem and present a multitude of open problems in the realm of the Partial Digest problem.