Approximation algorithms for a genetic diagnostics problem

被引:1
作者
Kosaraju, SR
Schaffer, AA
Biesecker, LG
机构
[1] Natl Human Genome Res Inst, NIH, Baltimore, MD 21224 USA
[2] Natl Human Genome Res Inst, NIH, Bethesda, MD USA
[3] Johns Hopkins Univ, Dept Comp Sci, Baltimore, MD 21218 USA
关键词
set cover; genetics; algorithms; monosomy; trisomy; genotyping;
D O I
10.1089/cmb.1998.5.9
中图分类号
Q5 [生物化学];
学科分类号
071010 ; 081704 ;
摘要
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.
引用
收藏
页码:9 / 26
页数:18
相关论文
共 23 条
[1]   Automated selection of short tandem repeat polymorphism markers for whole genome screening for segmental aneusomy [J].
Biesecker, LG ;
Schaffer, AA .
HUMAN HEREDITY, 1997, 47 (02) :76-85
[2]  
BIESECKER LG, 1966, AM J HUM GENET, V59, pA50
[3]   DETERMINATION OF GENE DOSAGE BY A QUANTITATIVE ADAPTATION OF THE POLYMERASE CHAIN-REACTION (GD-PCR) - RAPID DETECTION OF DELETIONS AND DUPLICATIONS OF GENE-SEQUENCES [J].
CELI, FS ;
COHEN, MM ;
ANTONARAKIS, SE ;
WERTHEIMER, E ;
ROTH, J ;
SHULDINER, AR .
GENOMICS, 1994, 21 (02) :304-310
[4]  
Chvatal V., 1979, Mathematics of Operations Research, V4, P233, DOI 10.1287/moor.4.3.233
[5]  
Cohen O, 1996, HUM GENET, V97, P659
[6]  
*COUNC REG NETW GE, 1994, CORN MIN DAT SET REP
[7]  
Feige U., 1996, Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, P314, DOI 10.1145/237814.237977
[8]   THE DETECTION OF SUBTELOMERIC CHROMOSOMAL REARRANGEMENTS IN IDIOPATHIC MENTAL-RETARDATION [J].
FLINT, J ;
WILKIE, AOM ;
BUCKLE, VJ ;
WINTER, RM ;
HOLLAND, AJ ;
MCDERMID, HE .
NATURE GENETICS, 1995, 9 (02) :132-140
[9]  
Gardner RJM, 1996, OXFORD MONOGRAPHS ME, V29
[10]   THE 1993-94 GENETHON HUMAN GENETIC-LINKAGE MAP [J].
GYAPAY, G ;
MORISSETTE, J ;
VIGNAL, A ;
DIB, C ;
FIZAMES, C ;
MILLASSEAU, P ;
MARC, S ;
BERNARDI, G ;
LATHROP, M ;
WEISSENBACH, J .
NATURE GENETICS, 1994, 7 (02) :246-339