Name
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 a 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. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1089/cmb.1998.5.9 | Journal of Computational Biology |
Keywords | Field | DocType |
genetics,set cover,local search,greedy heuristic | Approximation algorithm,Theoretical computer science,Bioinformatics,Mathematics | Conference |
Volume | Issue | ISSN |
5.0 | 1 | 1066-5277 |
Citations | PageRank | References |
0 | 0.34 | 5 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| S. Rao Kosaraju | 1 | 1403 | 243.78 |
| Alejandro A. Schäffer | 2 | 827 | 136.66 |
| Leslie G. Biesecker | 3 | 19 | 2.44 |