Partitioning K clones
Laxmi Parida, Bud Mishra · 1998
Given a set of m molecules, derived from K homologous clones, we wish to partition these molecules into K populations, each giving rise to distinct ordered restriction maps, thus providing simple means for stuclying biological variations.With the emergence of single molecule methods, such as optical mapping, that wn create individual ordered restriction maps reliably and with high throughput, it becomes interesting to study the related algorithmic problems-In particular, we provide a complete computational complezity analysis of the "Kpopulations"problem as well as some simple polynomial heuristics, while ezposing the relations among various error sources that the optical mapping approach may need to cope with.We believe that these results will be of interest to computational biologists in devising better algorithms, to biochemists in understanding the tradeoffs among the error sources andfinally, to biologists in creating reliable protocols for population study.