Fast and cheap genome wide haplotype construction via optical mapping

T. S. Anantharaman, V. Mysoref, B. Mishra

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We describe an efficient algorithm to construct genome wide haplotype restriction maps of an individual by aligning single molecule DNA fragments collected with Optical Mapping technology. Using this algorithm and small amount of genomic material, we can construct the parental haplotypes for each diploid chromosome for any individual. Since such haplotype maps reveal the polymorphisms due to single nucleotide differences (SNPs) and small insertions and deletions (RFLPs), they are useful in association studies, studies involving genomic instabilities in cancer, and genetics, and yet incur relatively low cost and provide high throughput. If the underlying problem is formulated as a combinatorial optimization problem, it can be shown to be NP-complete (a special case of /("-population problem). But by effectively exploiting the structure of the underlying error processes and using a novel analog of the Baum-Welch algorithm for HMM models, we devise a probabilistic algorithm with a time complexity that is linear in the number of markers for an e-approximate solution. The algorithms were tested by constructing the first genome wide haplotype restriction map of the microbe T. pseudoana, as well as constructing a haplotype restriction map of a 120 Mb region of Human chromosome 4. The frequency of false positives and false negatives was estimated using simulated data. The empirical results were found very promising.

Original languageEnglish (US)
Title of host publicationProceedings of the Pacific Symposium on Biocomputing 2005, PSB 2005
Number of pages12
StatePublished - 2005
Event10th Pacific Symposium on Biocomputing, PSB 2005 - Big Island of Hawaii, United States
Duration: Jan 4 2005Jan 8 2005

Publication series

NameProceedings of the Pacific Symposium on Biocomputing 2005, PSB 2005


Other10th Pacific Symposium on Biocomputing, PSB 2005
Country/TerritoryUnited States
CityBig Island of Hawaii

ASJC Scopus subject areas

  • Computational Theory and Mathematics
  • Biomedical Engineering


Dive into the research topics of 'Fast and cheap genome wide haplotype construction via optical mapping'. Together they form a unique fingerprint.

Cite this