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

BMC Bioinformatics

Table 10 Comparison of the alignment results of Nexus with other tools that support read alignment to the pan-genome in some form

Tool	Avg. nr. of text occurrences/read	Avg. nr. of graph occurrences/read	Fraction of aligned reads	Performance		Peak RAM usage [GiB]
Tool	Avg. nr. of text occurrences/read	Avg. nr. of graph occurrences/read	Fraction of aligned reads	[reads/s]	[text occs/s]	Peak RAM usage [GiB]
PuffAligner	11.79	Not reported	98.17%	7 216	85 724	62.44
A4	Not supported	0.90	89.39%	2 793	Not supp.	38.57
BWA-MEM	20.37/19.57	Not applicable	99.95/99.60%	1 430	29 113/27 975	49.80
Bowtie 2	9.92	Not applicable	99.56%	2 591	25 705	40.08
Giraffe	7.80/7.68	Not reported	98.36/96.95%	18	143/141	284.53
Nexus, K = 0	28.38	0.90	89.39%	13 324	378 198	90.71
Nexus, K = 1	94.01	2.14	95.11%	3 274	307 831	90.71
Nexus, K = 2	228.05	7.88	96.69%	1 145	261 124	98.08
Nexus, K = 3	450.76	23.17	97.47%	472	212 799	99.08
Nexus, K = 4	782.70	46.56	97.98%	199	156 133	100.59

For Nexus, we perform approximate pattern matching with different maximum allowed edit distances: \(K=\{0,1,2,3,4\}\). We ran 10 experiments for aligning 100 000 Illumina reads of length 101 bp as well as their reverse complement to the pan-genome of 10 human genomes. The pan-genome dBGs are built for \(k=25\), Nexus’ additional parameters are \(s_{ cp } = 128\) and \(s_{\textrm{SA}} = 16\). In terms of alignment output, we report the average number of reported text occurrences (i.e., in the form of a coordinate with respect to one of the input sequences) per read, the average number of graph occurrences (i.e., in the form of a node path) per read, and the fraction of reads that has at least one occurrence. In terms of performance, we report the average number of reads aligned per second, the average number of text occurrences reported per second, and the peak RAM usage of the alignment process. For BWA-MEM and Giraffe, two sets of text occurrences are reported: one with clipped alignments included and one with clipped alignments filtered out. For Bowtie 2 and Giraffe, the maximum number of alignments per read is capped at 10
The best result in each column is indicated in bold

ISSN: 1471-2105