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

BMC Bioinformatics

Table 7 Overview of the components of Nexus’ data structure, with their respective memory usage

Component	Memory usage per entry [bits]	Number of entries		Total for 10 human genomes (GiB)
Component	Memory usage per entry [bits]	General	10 human genomes	Total for 10 human genomes (GiB)
Bidirectional FM-index	19.75 + 64/\(s_{\textrm{SA}}\)	n	~ 30 billion bp	83.89
\(\textrm{G}\) \(\textrm{B}\) \(\textrm{B}^r\) \(\textrm{IDmap}\) \(\textrm{IDmap}^r\)	192 1.25 1.25 64 32	\|V\| n n \(\|V\| + \|V\|_ {cp}\) \|V\|	~ 66 million nodes ~ 30 billion bp ~ 30 billion bp ~ 137 million k-mers ~ 66 million nodes	1.48 4.42 4.42 1.02 252.16 MiB
Subtotal graph elements	-	-	-	11.57
Total	-	-	-	95.46

For each component, we indicate its number of entries and the number of bits per entry. The number of entries and memory usage of each component is illustrated for the pan-genome of 10 human genomes (\(s_{\textrm{SA}} = 16\), \(s_{ cp } = 128\), \(k=25\))

ISSN: 1471-2105