A Probabilistic Analysis of False Positives
in Genomic Map Alignment and Validation

Thomas Anantharaman
Dept of Biostatistics and Medical Informatics
University of Wisconsin, Madison


In the recent years, genome-wide shot-gun optical mapping of several 
microorganisms have led to sequence-ready high-resolution restriction
maps that directly facilitated sequence assembly avoiding gaps and 
compressions, speeding up finishing and validated shotgun sequence
assembly. A good-quality human map is likely to play a critical role in 
validating several currently available but unverified sequences.

A critical component of the map assembly process processes involves 
accurately bounding the false positive probability that two maps that
appear to match are in fact unrelated. It allows the space of possible map 
assemblies to be searched efficiently using a greedy search
algorithm combined with only limited amounts of backtracking.

We derive a tight bound on this false positive probability that 
characterizes the sharp transition from infeasible (exponential search 
complexity) to feasible (polynomial search complexity) experimental error 
rates. We outline a map assembly algorithm based on this false positive 
bound that runs in sub-quadratic time.

A brief cv and list of publications is available online at:
http://www.biostat.wisc.edu/faculty/anantharaman_thomas.html