File(s) under permanent embargo
Microscopy as a statistical, Rényi-Ulam, half-lie game: a new heuristic search strategy to accelerate imaging
journal contribution
posted on 2017-11-07, 00:00 authored by Daniel DrummDaniel Drumm, Andrew D GreentreeFinding a fluorescent target in a biological environment is a common and pressing microscopy problem. This task is formally analogous to the canonical search problem. In ideal (noise-free, truthful) search problems, the well-known binary search is optimal. The case of half-lies, where one of two responses to a search query may be deceptive, introduces a richer, Rényi-Ulam problem and is particularly relevant to practical microscopy. We analyse microscopy in the contexts of Rényi-Ulam games and half-lies, developing a new family of heuristics. We show the cost of insisting on verification by positive result in search algorithms; for the zero-half-lie case bisectioning with verification incurs a 50% penalty in the average number of queries required. The optimal partitioning of search spaces directly following verification in the presence of random half-lies is determined. Trisectioning with verification is shown to be the most efficient heuristic of the family in a majority of cases.
History
Journal
Scientific reportsVolume
7Issue
1Article number
14652Pagination
1 - 13Publisher
Nature PublishingLocation
London, Eng.Publisher DOI
Link to full text
eISSN
2045-2322Language
engPublication classification
C Journal article; C1.1 Refereed article in a scholarly journalCopyright notice
2017, The AuthorsUsage metrics
Categories
No categories selectedKeywords
Licence
Exports
RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC