Optimizing exact genetic linkage computations

被引：63

作者：

Fishelson, M ^{[1
]}

Geiger, D ^{[1
]}

机构：

[1] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

来源：

JOURNAL OF COMPUTATIONAL BIOLOGY | 2004年 / 11卷 / 2-3期

关键词：

Bayesian networks; DAG models; genetic linkage analysis; SUPERLINK; treewidth;

D O I：

10.1089/1066527041410409

中图分类号：

Q5 [生物化学];

学科分类号：

071010 ; 081704 ;

摘要：

Genetic linkage analysis is a challenging application which requires Bayesian networks consisting of thousands of vertices. Consequently, computing the probability of data, which is needed for learning linkage parameters, using exact computation procedures calls for an extremely efficient implementation that carefully optimizes the order of conditioning and summation operations. In this paper, we present the use of stochastic greedy algorithms for optimizing this order. Our algorithm has been incorporated into the newest version of SUPERLINK, which is a fast genetic linkage program for exact likelihood computations in general pedigrees. We demonstrate an order of magnitude improvement in run times of likelihood computations using our new optimization algorithm and hence enlarge the class of problems that can be handled effectively by exact computations.

引用

页码：263 / 275

页数：13

共 38 条

[1]

Andersen SK., 1989, Proc Elev Int Jt Conf Artif Intell, V2, P1080

[2]

ARNBORG S, 1985, BIT, V25, P2, DOI 10.1007/BF01934985

[3] COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE [J].

ARNBORG, S ;

CORNEIL, DG ;

PROSKUROWSKI, A .

SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02) :277-284

[4] A sufficiently fast algorithm for finding close to optimal clique trees [J].

Becker, A ;

Geiger, D .

ARTIFICIAL INTELLIGENCE, 2001, 125 (1-2) :3-17

[5]

BECKER A, 1998, HUM HERED, V48, P4960

[6]

Bodlaender H., 2001, P 17 C UNC ART INT, P32

[7] Mutant chromatin remodeling protein SMARCAL1 causes Schimke immuno-osseous dysplasia [J].

Boerkoel, CF ;

Takashima, H ;

John, J ;

Yan, J ;

Stankiewicz, P ;

Rosenbarker, L ;

André, JL ;

Bogdanovic, R ;

Burguet, A ;

Cockfield, S ;

Cordeiro, I ;

Fründ, S ;

Illies, F ;

Joseph, M ;

Kaitila, I ;

Lama, G ;

Loirat, C ;

McLeod, DR ;

Milford, DV ;

Petty, EM ;

Rodrigo, F ;

Saraiva, JM ;

Schmidt, B ;

Smith, GC ;

Spranger, J ;

Stein, A ;

Thiele, H ;

Tizard, J ;

Weksberg, R ;

Lupski, JR ;

Stockton, DW .

NATURE GENETICS, 2002, 30 (02) :215-220

[8] Mutant DNA-binding domain of HSF4 is associated with autosomal dominant lamellar and Marner cataract [J].

Bu, L ;

Jin, YP ;

Shi, YF ;

Chu, RY ;

Ban, AR ;

Eiberg, H ;

Andres, L ;

Jiang, HS ;

Zheng, GY ;

Qian, MQ ;

Cui, B ;

Xia, Y ;

Liu, J ;

Hu, LD ;

Zhao, GP ;

Hayden, MR ;

Kong, XY .

NATURE GENETICS, 2002, 31 (03) :276-278

[9] PROBABILITY FUNCTIONS ON COMPLEX PEDIGREES [J].

CANNINGS, C ;

THOMPSON, EA ;

SKOLNICK, MH .

ADVANCES IN APPLIED PROBABILITY, 1978, 10 (01) :26-61

[10]

COTTINGHAM RW, 1993, AM J HUM GENET, V53, P252

← 1 2 3 4 →