Partitioning K clones: Hardness results and practical algorithms for the K-populations problem

Laxmi Parida, Bud Mishra

Research output: Contribution to conferencePaper

Abstract

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 studying biological variations. With the emergence of single molecule methods, such as optical mapping, that can 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 complexity analysis of the `K-populations' problem as well as some simple polynomial heuristics, while exposing 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 and finally, to biologists in creating reliable protocols for population study.

Original languageEnglish (US)
Pages192-201
Number of pages10
StatePublished - 1998
EventProceedings of the 1998 2nd Annual International Conference on Computational Molecular Biology - New York, NY, USA
Duration: Mar 22 1998Mar 25 1998

Other

OtherProceedings of the 1998 2nd Annual International Conference on Computational Molecular Biology
CityNew York, NY, USA
Period3/22/983/25/98

ASJC Scopus subject areas

  • Computer Science(all)
  • Biochemistry, Genetics and Molecular Biology(all)

Fingerprint Dive into the research topics of 'Partitioning K clones: Hardness results and practical algorithms for the K-populations problem'. Together they form a unique fingerprint.

  • Cite this

    Parida, L., & Mishra, B. (1998). Partitioning K clones: Hardness results and practical algorithms for the K-populations problem. 192-201. Paper presented at Proceedings of the 1998 2nd Annual International Conference on Computational Molecular Biology, New York, NY, USA, .