Skip to main content

Table 9 Performance of A4 and Nexus for pattern matching against the graph for different maximum allowed edit distances: \(K=\{0,1,2,3,4\}\)

From: Pan-genome de Bruijn graph using the bidirectional FM-index

Maximum edit distance

A4 performance [reads/s]

Nexus performance [reads/s]

APM runtime [s]

Node path finding runtime [s]

Post-processing runtime [s]

K = 0

2 793 ± 278

 

13 324 ± 880

 
 

2.60 (34%)

2.03 (27%)

2.93 (39%)

K = 1

Not supported

 

3 274 ± 128

 
 

11.31 (37%)

3.80 (12%)

15.52 (51%)

K = 2

Not supported

 

1 145 ± 31

 
 

32.97 (38%)

9.36 (11%)

45.12 (51%)

K = 3

Not supported

 

472 ± 13

 
 

87.89 (41%)

23.17 (11%)

101.08 (48%)

K = 4

Not supported

 

199 ± 4

 
 

253.23 (51%)

52.27 (10%)

196.15 (39%)

  1. We aligned 100 000 Illumina reads (length 101 bp) and their reverse complement to the pan-genome graph of 10 human genomes (\(k=25\), \(s_{ cp } = 128\) and \(s_{\textrm{SA}} = 16\) – last two parameters only apply to Nexus). Runs were repeated 10 times. Performance (expressed in reads per second) is reported along with the 95% confidence intervals. Additionally, for Nexus, we provide a breakdown of the total runtime into the runtime for approximate pattern matching using the underlying FM-index, identifying the corresponding node path in the graph, and post-processing (identifying and filtering text occurrences)
Back to article page

BMC Bioinformatics

ISSN: 1471-2105

Contact us