Summery of the results

We compared our Haplotyping query to the SuperMLink query and to Ma'ayan's Haplotyping query.

In this section all tests were done with K=1, meaning only one possible haplotype was required.

We also tested our program for the time consumption on several pedigrees with different parameters. The graphs obtained can be seen here.

The tests were processed on AMD, 1.68 GHZ, 224 MB of RAM, XP.

 

bullet

  Haplotyping query  vs. SuperMLink

 

Comparison between the results obtained by MPE query and the standard algorithm of SuperLink for likelihood computation:

Experiment A:

File

#People

#Loci haplotyping algorithm

#Loci likelihood algorithm

#Nodes in BN haplotyping algorithm

#Nodes in BN likelihood algorithm

Run Time haplotyping algorithm

Run Time likelihood algorithm

EA0

57

1

1

106

255

0.015

0.046

EA1

57

4

4

450

528

0.031

0.031

EA2

57

5

5

531

608

0.046

0.031

EA3

57

6

6

628

686

0.062

0.046

EA4

57

7

7

747

750

0.062

0.062

EA5

57

9

9

946

919

0.062

0.203

EA6

57

11

11

1181

1109

0.14

1.234

EA7

57

13

13

1396

1310

0.281

0.796

EA8

57

17

17

1774

1626

0.468

0.265

EA9

57

36

36

3784

3265

5.625

31.062

EA10

57

37

37

3890

3377

10.187

90.218

EA11

57

42

42

4412

3814

17.218

133.562

 

Experiment B:

File

#People

#Loci haplotyping algorithm

#Loci likelihood algorithm

#Nodes in BN haplotyping algorithm

#Nodes in BN likelihood algorithm

Run Time haplotyping algorithm

Run Time likelihood algorithm

EB0

100

4

5

682

886

0.046

0.046

EB1

100

5

6

839

1021

0.078

0.25

EB2

100

9

10

1507

1638

0.109

0.421

EB3

100

11

12

1854

1958

0.359

2.328

EB4

100

12

13

2035

2102

0.312

1.39

EB5

100

13

14

2193

2247

0.343

1.062

EB6

100

14

15

2377

2401

2.171

2.734

EB7

100

15

16

2575

2571

1.265

5

EB8

100

16

17

2767

2739

1.203

5.421

EB9

100

17

18

2931

2898

3.39

3.734

EB10

100

18

19

3119

3076

1.156

6.968

EB11

100

19

20

3285

3239

6.937

10

Experiment C:

File

#People

#Loci haplotyping algorithm

#Loci likelihood algorithm

#Nodes in BN haplotyping algorithm

#Nodes in BN likelihood algorithm

Run Time haplotyping algorithm

Run Time likelihood algorithm

EC1

100

6

7

1237

1447

0.109

0.25

EC2

100

7

8

1327

1520

0.093

0.156

EC3

100

9

10

1794

1984

1.125

1.859

EC4

100

14

15

2309

2384

0.171

0.265

EC5

20

14

15

565

585

0.437

1.062

EC6

15

19

20

567

581

0.171

0.625

EC7

15

21

22

627

641

0.5

0.687

EC8

150

7

8

1757

2019

0.109

0.203

EC9

150

9

10

2227

2451

0.171

0.265

EC10

5

99

100

899

881

0.062

0.093

EC11

5

109

110

985

966

0.062

0.062

Experiment D:

File

#People

#Loci haplotyping algorithm

#Loci likelihood algorithm

#Nodes in BN haplotyping algorithm

#Nodes in BN likelihood algorithm

Run Time haplotyping algorithm

Run Time likelihood algorithm

ED0

5

99

100

1047

986

0.062

0.093

ED1

5

109

110

1154

1088

0.078

0.078

ED2

5

119

120

1260

1184

0.078

0.109

ED3

5

129

130

1375

1288

0.062

0.156

ED4

5

139

140

1476

1380

0.093

0.125

ED5

5

149

150

1571

1468

0.093

0.125

ED6

5

159

160

1690

1570

0.109

0.125

ED7

5

169

170

1802

1672

0.125

0.156

ED8

5

179

180

1902

1762

0.093

0.171

ED9

5

189

190

2006

1862

0.109

0.234

ED10

5

199

200

2115

1962

0.093

0.218

ED11

5

209

210

2207

2050

0.125

0.218

Experiment GB:

File

#People

#Loci haplotyping algorithm

#Loci likelihood algorithm

#Nodes in BN haplotyping algorithm

#Nodes in BN likelihood algorithm

Run Time haplotyping algorithm

Run Time likelihood algorithm

GB_27_0

15

1

2

48

 68

0.046

0.015

 GB_67_0

15

1

2

40

 84

0.031

0.062

 GB_90_0

15

1

2

20

 63

0.046

 0.015

 GB_90_1

15

3

4

65

 108

0.031

 0.062

 GB_90_2

15

5

6

120

 163

0.031

 0.062

GB_90_3

15

7

8

159

 202

0.031

 0.046

Experiment GC: 

File

#People

#Loci haplotyping algorithm

#Loci likelihood algorithm

#Nodes in BN haplotyping algorithm

#Nodes in BN likelihood algorithm

Run Time haplotyping algorithm

Run Time likelihood algorithm

GC_86_0

29

1

2

56

 126

0.031

0.046

GC_86_1

29

3

4

162

 232

0.031

0.046 

GC_86_2

29

5

6

259

 326

0.031

0.046 

GC_86_3

29

7

8

375

 442

0.062

0.046 

GC_69_0

29

1

2

69

 134

0.031

0.046

GC_69_1

29

3

4

192

 255

0.046

0.062 

GC_69_2

29

5

6

301

 365

0.046

0.265 

GC_69_3

29

7

8

439

 503

0.125

0.453 

GC_31_0

29

1

2

74

 140

0.015

0.062 

 

bullet

 Our Haplotyping query vs. Ma'ayan's version.

Comparison between the results obtained by our MPE query and haplotyping of SuperLink:

Experiment A:

File

#People

#Loci haplotyping algorithm

#Nodes in BN haplotyping algorithm

Run Time of Haplotyping

Run Time of SuperLink

MPE Probability

EA0

57

1

106

0.015

0.015

-129.015

EA1

57

4

450

0.031

0.046

-385.071

EA2

57

5

531

0.015

0.062

-486.774

EA3

57

6

628

0.031

0.046

-578.961

EA4

57

7

747

0.031

0.078

-660.161

EA5

57

9

946

0.031

0.062

-837.942

EA6

57

11

1181

0.14

0.156

-1038.33

EA7

57

13

1396

0.281

0.328

-1233.69

EA8

57

17

1774

0.468

0.593

-1606.83

EA9

57

36

3784

5.625

10.562

-3381.62

EA10

57

37

3890

10.187

8.531

-3505.21

EA11

57

42

4412

17.218

24.531

-3970.53

Experiment B:

File

#People

#Loci haplotyping algorithm

#Nodes in BN haplotyping algorithm

Run Time of Haplotyping

Run Time of SuperLink

MPE Probability

EB0

100

4

682

0.046

0.046

 

-847.087

EB1

100

5

839

0.078

0.109

-1124.34

EB2

100

9

1507

0.109

0.171

-2008.4

EB3

100

11

1854

0.359

0.468

-2388.22

EB4

100

12

2035

0.312

0.375

-2553.08

EB5

100

13

2193

0.343

0.453

-2791.84

EB6

100

14

2377

2.171

1.546

-2995.11

EB7

100

15

2575

1.265

1.406

-3188.68

EB8

100

16

2767

1.203

2.265

-3385.86

EB9

100

17

2931

3.39

3.218

-3570.57

EB10

100

18

3119

1.156

3.25

-3824.98

EB11

100

19

3285

6.937

5.125

-4125.61

Experiment C: 

File

#People

#Loci haplotyping algorithm

#Nodes in BN haplotyping algorithm

Run Time of Haplotyping

Run Time of SuperLink

MPE Probability

EC1

100

6

1237

0.109

0.109

-556.003

EC2

100

7

1327

0.093

0.093

-650.764

EC3

100

9

1794

1.125

0.781

-879.444

EC4

100

14

2309

0.171

0.203

-3067.73

EC5

20

14

565

0.437

0.437

-283.433

EC6

15

19

567

0.171

0.234

-261.797

EC7

15

21

627

0.5

0.968

-292.652

EC8

150

7

1757

0.109

0.14

-1923.46

EC9

150

9

2227

0.171

0.218

-2566.4

EC10

5

99

899

0.062

0.125

-1101.48

EC11

5

109 985 0.031 0.078 -12054.59

Experiment D:

File

#People

#Loci haplotyping algorithm

#Nodes in BN haplotyping algorithm

Run Time of Haplotyping

Run Time of SuperLink

MPE Probability

ED0

5

99

1047

0.062

0.156

-934.527

ED1

5

109

1154

0.078

0.156

-1031.35

ED2

5

119

1260

0.078

0.14

-1124.42

ED3

5

129

1375

0.062

0.14

-1212.99

ED4

5

139

1476

0.093

0.14

-1297.85

ED5

5

149

1571

0.093

0.156

-1401.24

ED6

5

159

1690

0.109

0.203

-1490.95

ED7

5

169

1802

0.125

0.187

-1591.42

ED8

5

179

1902

0.093

0.203

-1674.47

ED9

5

189

2006

0.109

0.25

-1753.73

ED10

5

199

2115

0.093

0.25

-1838.85

ED11

5

209

2207

0.125

0.265

-1936.54

Experiment GB:

File

#People

#Loci haplotyping algorithm

#Nodes in BN haplotyping algorithm

Run Time of Haplotyping

Run Time of SuperLink

MPE Probability

GB_27_0

15

1

48

0.046

0.062

-27.1939

 GB_67_0

15

1

40

0.031

0.046

-27.0576

 GB_90_0

15

1

20

0.046

 0.015

-31.8896

 GB_90_1

15

3

65

0.031

 0.125

-62.3893

 GB_90_2

15

5

120

0.031

 0.046

-91.8729

GB_90_3

15

7

159

0.031

 0.031

-133.593

Experiment GC:

File

#People

#Loci haplotyping algorithm

#Nodes in BN haplotyping algorithm

Run Time of Haplotyping

Run Time of SuperLink

MPE Probability

GC_86_0

29

1

56

0.031

0.015

-56.4812

GC_86_1

29

3

162

0.031

 0.015

-161.628

GC_86_2

29

5

259

0.031

0.015

-271.15

GC_86_3

29

7

375

0.062

 0.062

-354.082

GC_69_0

29

1

69

0.031

 0.031

-71.2522

GC_69_1

29

3

192

0.046

 0.031

-146.271

GC_69_2

29

5

301

0.046

 0.046

-214.076

GC_69_3

29

7

439

0.125

 0.14

-295.631

GC_31_0

29

1

74

0.015

0.015

-45.8126

 

bullet

Time consumption by the Haplotyping query for vary parameters:

bullet

The following graph shows the time consumption by our Haplotyping query for vary pedigrees as a function of the number of solutions(K) required:

 
bullet

The following graph shows the time consumption by our Haplotyping query for vary pedigrees: where the number of solutions(K) determined to be 5, 10 or 15 and for each of these Ks the epsilon changes in range of 1-60. Each series in the graph represents a pedigree and required K (number of solutions) for it.

It can be seen from the graph, that the optimum epsilon is 3. This epsilon produces the fastest solution and keeps them very close to the highest probability that can be obtained by the haplotyping query.

 

 
bullet

The following graph shows the time consumption and the number of solution as a function of the depth of the search:

       

 

 

 

 

 

 

 

 

 

 

 

Back to main page.