title: Approximation algorithms for a genetic diagnostics problem.
abstract: We define and study a combinatorial problem called WEIGHTED DIAGNOSTIC COVER (WDC) that models the use of a laboratory technique called genotyping in the diagnosis of an important class of chromosomal aberrations. An optimal solution to WDC would enable us to define a genetic assay that maximizes the diagnostic power for a specified cost of laboratory work. We develop approximation algorithms for WDC by making use of the well-known problem SET COVER for which the greedy heuristic has been extensively studied. We prove worst-case performance bounds on the greedy heuristic for WDC and for another heuristic we call directional greedy. We implemented both heuristics. We also implemented a local search heuristic that takes the solutions obtained by greedy and dir-greedy and applies swaps until they are locally optimal. We report their performance on a real data set that is representative of the options that a clinical geneticist faces for the real diagnostic problem. Many open problems related to WDC remain, both of theoretical interest and practical importance.
authors.affiliation: Department of Computer Science, Johns Hopkins University, Baltimore, Maryland, USA.
authors.forename: S R
authors.initials: SR
authors.lastname: Kosaraju
authors.forename: A A
authors.initials: AA
authors.lastname: Schäffer
authors.forename: L G
authors.initials: LG
authors.lastname: Biesecker
mesh_terms: D000465:Algorithms; D002869:Chromosome Aberrations / Q000235:genetics*; D003201:Computers; D030342:Genetic Diseases, Inborn / Q000175:diagnosis* / Q000235:genetics; D005819:Genetic Markers / Q000235:genetics; D005838:Genotype; D006801:Humans; D008607:Intellectual Disability / Q000235:genetics; D008957:Models, Genetic; D009006:Monosomy / Q000235:genetics; D010641:Phenotype; D012984:Software; D014314:Trisomy / Q000235:genetics
chemical_list: D005819:Genetic Markers