Approximation algorithms for a genetic diagnostics problem.
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.
Kosaraju
S R
SR
Department of Computer Science, Johns Hopkins University, Baltimore, Maryland, USA.
Schäffer
A A
AA
Biesecker
L G
LG
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
D005819:Genetic Markers