Exact score distribution computation for ontological similarity searches

BMC Bioinformatics

Table 1 Runtime in milliseconds averaged over 20 runs comparing the naive, exact, and sampled distribution computation for q = 2,3,4, and 5

Runtime Analysis with the HPO
				*runtime in milliseconds*
OMIM ID	$\| T \|$	$\| T^{I M P L} \|$	$\| U \|$	naive	exact	sampled*
q = 2
264300	5	17	16	3779	4	50
613124	7	36	36	3794	6	53
113450	12	80	72	3789	6	65
129500	20	66	61	3702	15	89
q = 3
264300	5	17	16	~ 1.2 · 10⁷	4	49
613124	7	36	36	~ 1.2 · 10⁷	6	53
113450	12	80	72	~ 1.2 · 10⁷	19	66
129500	20	66	61	~ 1.2 · 10⁷	15	79
q = 4
264300	5	17	16	-	5	46
613124	7	36	36	-	20	55
113450	12	80	72	-	250	65
129500	20	66	61	-	135	77
q = 5
264300	5	17	16	-	7	48
613124	7	36	36	-	141	54
113450	12	80	72	-	3896	63
129500	20	66	61	-	1776	79

Four OMIM diseases with a varying number of annotated HPO terms ( $| T |$ ) were used; 264300: 17-β Hydroxysteroid Dehydrogenase III deficiency, 613124: Hydrops fetalis, nonimmune, with gracile bones and dysmorphic features, 113450: Brachydactyly-distal symphalangism syndrome, 129500: Ectodermal dysplasia 2, hidrotic. Entries denoted "-" were terminated after four hours. *Sampling with 10⁵ repetitions.

ISSN: 1471-2105