False positives in genomic map assembly and sequence validation

Thomas Anantharaman; Bud Mishra

doi:10.1007/3-540-44696-6_3

False positives in genomic map assembly and sequence validation

Thomas Anantharaman, Bud Mishra

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English (US)
Title of host publication	Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings
Editors	Bernard M. E. Moret, Olivier Gascuel
Publisher	Springer Verlag
Pages	27-40
Number of pages	14
ISBN (Print)	3540425160
DOIs	https://doi.org/10.1007/3-540-44696-6_3
State	Published - 2001
Event	1st International Workshop on Algorithms in Bioinformatics, WABI 2001 - Arhus, Denmark Duration: Aug 28 2001 → Aug 31 2001

Publication series

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

Other

Other	1st International Workshop on Algorithms in Bioinformatics, WABI 2001
Country/Territory	Denmark
City	Arhus
Period	8/28/01 → 8/31/01

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/3-540-44696-6_3

Cite this

Anantharaman, T., & Mishra, B. (2001). False positives in genomic map assembly and sequence validation. In B. M. E. Moret, & O. Gascuel (Eds.), Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings (pp. 27-40). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2149). Springer Verlag. https://doi.org/10.1007/3-540-44696-6_3

False positives in genomic map assembly and sequence validation. / Anantharaman, Thomas; Mishra, Bud.
Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings. ed. / Bernard M. E. Moret; Olivier Gascuel. Springer Verlag, 2001. p. 27-40 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 2149).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Anantharaman, T & Mishra, B 2001, False positives in genomic map assembly and sequence validation. in BME Moret & O Gascuel (eds), Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 2149, Springer Verlag, pp. 27-40, 1st International Workshop on Algorithms in Bioinformatics, WABI 2001, Arhus, Denmark, 8/28/01. https://doi.org/10.1007/3-540-44696-6_3

Anantharaman T, Mishra B. False positives in genomic map assembly and sequence validation. In Moret BME, Gascuel O, editors, Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings. Springer Verlag. 2001. p. 27-40. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/3-540-44696-6_3

Anantharaman, Thomas ; Mishra, Bud. / False positives in genomic map assembly and sequence validation. Algorithms in Bioinformatics - First International Workshop, WABI 2001 Århus Denmark, August 28-31, 2001 Proceedings. editor / Bernard M. E. Moret ; Olivier Gascuel. Springer Verlag, 2001. pp. 27-40 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{82053cf88dab4f6189541824a192e3b4,

title = "False positives in genomic map assembly and sequence validation",

abstract = "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.",

author = "Thomas Anantharaman and Bud Mishra",

note = "Publisher Copyright: {\textcopyright} Springer-Verlag Berlin Heidelberg 2001. Copyright: Copyright 2016 Elsevier B.V., All rights reserved.; 1st International Workshop on Algorithms in Bioinformatics, WABI 2001 ; Conference date: 28-08-2001 Through 31-08-2001",

year = "2001",

doi = "10.1007/3-540-44696-6_3",

language = "English (US)",

isbn = "3540425160",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "27--40",

editor = "Moret, {Bernard M. E.} and Olivier Gascuel",

booktitle = "Algorithms in Bioinformatics - First International Workshop, WABI 2001 {\AA}rhus Denmark, August 28-31, 2001 Proceedings",

}

TY - GEN

T1 - False positives in genomic map assembly and sequence validation

AU - Anantharaman, Thomas

AU - Mishra, Bud

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 -

False positives in genomic map assembly and sequence validation

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this