TY - GEN

T1 - False positives in genomic map assembly and sequence validation

AU - Anantharaman, Thomas

AU - Mishra, Bud

N1 - Publisher Copyright:
© Springer-Verlag Berlin Heidelberg 2001.
Copyright:
Copyright 2016 Elsevier B.V., All rights reserved.

PY - 2001

Y1 - 2001

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84959040574&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84959040574&partnerID=8YFLogxK

U2 - 10.1007/3-540-44696-6_3

DO - 10.1007/3-540-44696-6_3

M3 - Conference contribution

AN - SCOPUS:84959040574

SN - 3540425160

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 27

EP - 40

BT - Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings

A2 - Moret, Bernard M. E.

A2 - Gascuel, Olivier

PB - Springer Verlag

T2 - 1st International Workshop on Algorithms in Bioinformatics, WABI 2001

Y2 - 28 August 2001 through 31 August 2001

ER -