Skip to main content

Table 1 The distance between pairs of diploids computed by our three algorithms, and the time (in seconds) used for the computation.

From: Recombination-aware alignment of diploid individuals

   Cubic algorithm Synchronized -Matrix Synchronized -Diagonals
Length Mutations Distance Time Distance Time Distance Time
1000 21 21 19.190 21 0.040 21 0.001
2000 47 43 154.030 47 0.110 47 0.010
4000 85 79 1219.060 85 0.650 85 0.020
8000 174 - - 172 1.790 172 0.070
10000 218 - - 216 2.820 216 0.180
20000 408 - - 403 11.080 403 0.580
40000 777 - - 750 44.290 750 1.170
80000 1578 - - 1531 177.200 1531 4.630
100000 1994 - - 1935 276.960 1935 11.500
  1. Cubic algorithm is our implementation of the pair of haploids to diploid algorithm, Synchronized -Matrix is the straightforward implementation of the synchronized diploid to diploid distance, and Synchronized -Diagonals is the O(ND) time implementation of the same algorithm using the shortest detour technique.