Biomedical Engineering Reference
In-Depth Information
instances generated using the Hudson's program,
ms
[
23
], and harder instances de-
scribedin[
39
] which were generated to evaluate phasing algorithms. Real data
were obtained from the HapMap project and biological instances generated from
publicly available data (e.g., [
9
,
10
,
26
,
38
]). All problem instances were simpli-
fied in a preprocessing step, as described in Sect.
7.5.1
. The maximum number of
SNPs on the simplified instances is 188 and the maximum number of genotypes
is 94. For a more detailed description of problem instances and results, see other
literature [
17
,
31
,
32
].
The extensive comparison includes nine HIPP solvers: RPoly [
17
] version 1.2,
SHIPs [
31
] version 2, HaploPPH [
5
], Haplo-ASP [
12
], RTIP [
19
], SATlotyper [
36
]
version 0.1.1 b, HAPAR [
44
], PolyIP [
2
] and HybridIP [
3
]. Results were obtained
on an Intel Xeon 5160 server (3.0GHz, 4GB RAM) running Red Hat Enterprise
Linux WS 4. The CPU time is limited to 1,000 s.
Tab le
7.1
resumes the performance of exact HIPP solvers, stating the percentage
and the mean time required for solving the solved instances within 1,000 s. RPoly
is the HIPP tool capable of solving the largest number of instances. Clearly, the
SAT-based models are the best performing solvers. RPoly solves 1,165 instances
and SHIPs solves 1,116 of 1,183 instances. Taking into account the amount of time
that each solver requires, on average, to solve the non-aborted instances, we can
conclude that RPoly is also the fastest solver. The exponential ILP model, RTIP, is
significantly efficient for easy instances. Nonetheless, RTIP is not able to solve more
than 30% of the instances due to memory exhaustion. The performance of PolyIP
and HybridIP is similar, both solving around 40% of the instances.
SATlotyper is a more general HIPP solver, being able to solve haplotype infer-
ence problems on polyploids and polyallelic species. Therefore, SATlotyper was
not created to compete with exact HIPP solvers and is less optimized than SHIPs. In
particular, SATlotyper does not include the computation of the lower bound, which
is a crucial point to the good performance of SHIPs.
The fact that the best performing solvers are RPoly and SHIPs suggests that the
SAT-based techniques are the most adequate for solving the HIPP problem.
Tabl e 7. 1
Summary
of the performance of exact
HIPP solvers
Model
% solved instances
Average time (s)
RPoly
98.5%
3:53
SHIPs
94.3%
7:86
HaploPPH
79.1%
42:34
Haplo-ASP
73.5%
30:18
RTIP
68.0%
6:78
SATlotyper
66.9%
24:41
HAPAR
48.9%
39:90
PolyIP
40.2%
73:44
HybridIP
39.6%
72:94
Search WWH ::
Custom Search