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.

Is it necessary to perform surveillance endomyocardial biopsies in heart transplant recipients?

BACKGROUND: Routine surveillance endomyocardial biopsies to diagnose unsuspected rejection are performed at 3- to 12-month intervals after heart transplantation. From 1979 to 1989, surveillance biopsies were routinely performed as a part of the yearly evaluation. METHODS: A retrospective analysis of the follow-up data showed that "routine surveillance biopsies" had an extremely low yield, and, on the basis of the results of this study, we discontinued to perform surveillance biopsies beyond 6 months after transplantation. To validate these results, we compared the outcome of two groups of patients who had similar demographics and identical immunosuppression, except that in one group the surveillance biopsies were not performed. RESULTS: No difference was found in either actuarial survival rate or freedom from late rejection between the two groups. CONCLUSIONS: These findings confirm that routine surveillance heart biopsies beyond 6 months after transplantation are not necessary and they should be performed only if there is clinical suspicion of rejection or as part of a research protocol.