False positives in genomic map assembly and sequence validation

Thomas Anantharaman, Bud Mishra

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


This paper outlines an algorithm for whole genome order restriction optical map assembly. The algorithm can run very reliably in polynomial time by exploiting a strict limit on the probability that two maps that appear to overlap are in fact unrelated (false positives). The main result of this paper is a tight bound on the false positive probability based on a careful model of the experimental errors in the maps found in practice. Using this false positive probability bound, we show that the probability of failure to compute the correct map can be limited to acceptable levels if the input map error rates satisfy certain sharply delineated conditions. Thus careful experimental design must be used to ensure that whole genome map assembly can be done quickly and reliably.

Original languageEnglish (US)
Title of host publicationAlgorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings
EditorsBernard M. E. Moret, Olivier Gascuel
PublisherSpringer Verlag
Number of pages14
ISBN (Print)3540425160
StatePublished - 2001
Event1st International Workshop on Algorithms in Bioinformatics, WABI 2001 - Arhus, Denmark
Duration: Aug 28 2001Aug 31 2001

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other1st International Workshop on Algorithms in Bioinformatics, WABI 2001

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'False positives in genomic map assembly and sequence validation'. Together they form a unique fingerprint.

Cite this