Publications underpinning MetaGraph

Key publications describing the MetaGraph framework, compression algorithms, alignment methods and databases/sources.

If you are using MetaGraph or the index resources for your work, please cite:

Karasikov M, Mustafa H, Danciu D, Kulkov O, Zimmermann M, Barber C, Rätsch G, Kahles A. Efficient and accurate search in petabase-scale sequence repositories. Nature. 2025;647: 1036–1044. https://www.nature.com/articles/s41586-025-09603-w

BibTeX

@article{karasikov2025metagraph,
  title={Efficient and accurate search in petabase-scale sequence repositories},
  author={Karasikov, Mikhail and Mustafa, Harun and Danciu, Daniel and Kulkov, Oleksandr and Zimmermann, Marc and Barber, Christopher and R{\"a}tsch, Gunnar and Kahles, Andr{\'e}},
  journal={Nature},
  volume={647},
  number={8091},
  pages={1036--1044},
  year={2025},
  publisher={Nature Publishing Group},
  doi={10.1038/s41586-025-09603-w}
}

MetaGraph framework

The foundational architecture for petabase‑scale sequence search

Efficient and accurate search in petabase‑scale sequence repositories
Nature, 2025. DOI: 10.1038/s41586-025-09603-w
M. Karasikov; H. Mustafa; D. Danciu; O. Kulkov; M. Zimmermann; C. Barber; G. Rätsch; A. Kahles
Why it matters: Demonstrates practical feasibility of economical full‑text search in 67 petabase pairs of public sequence data, making biological archives searchable at scale.
OA: Open Access
MetaGraph: Indexing and Analysing Nucleotide Archives at Petabase‑scale
bioRxiv, 2020. DOI: 10.1101/2020.10.01.322164
M. Karasikov; H. Mustafa; D. Danciu; M. Zimmermann; C. Barber; G. Rätsch; A. Kahles
Why it matters: First end‑to‑end description of MetaGraph for petabase‑scale annotated de Bruijn‑graph indexing and search.

Graph annotation & compression

Compact representations and efficient encoding of graph labels

Sparse Binary Relation Representations for Genome Graph Annotation
Journal of Computational Biology, 27(4):626–639, 2020. DOI: 10.1089/cmb.2019.0324
M. Karasikov; H. Mustafa; A. Joudaki; S. Javadzadeh‑No; G. Rätsch; A. Kahles
Why it matters: Column‑hierarchical (Multi‑BRWT) compression—cornerstone for compact colored/annotated DBGs.
OA: PMCID: PMC7185347
Topology‑based sparsification of graph annotations (RowDiff)
Bioinformatics, 37(Suppl 1):i169–i176, 2021. DOI: 10.1093/bioinformatics/btab330
D. Danciu; M. Karasikov; H. Mustafa; A. Kahles; G. Rätsch
Why it matters: Exploits graph topology to sparsify labels—big annotation size reductions with fast queries.
OA: PMCID: PMC8346655
Dynamic compression schemes for graph coloring
Bioinformatics, 35(3):407–414, 2019. DOI: 10.1093/bioinformatics/bty632
H. Mustafa; I. Schilken; M. Karasikov; C. Eickhoff; G. Rätsch; A. Kahles
Why it matters: Early compact/dynamic color encoding that informed later MetaGraph annotation designs.
OA: PMCID: PMC6530811

Lossless counting & coordinates

Quantitative and positional information in graph indexes

Lossless indexing with counting de Bruijn graphs
Genome Research, 32(9):1754–1764, 2022. DOI: 10.1101/gr.276607.122
M. Karasikov; H. Mustafa; G. Rätsch; A. Kahles
Why it matters: Adds counts and coordinates; enables lossless quantitative and positional queries in MetaGraph.
OA: PMCID: PMC9528980

Sequence‑to‑graph alignment (MetaGraph)

Sensitive alignment methods for annotated graph search

Label‑guided seed‑chain‑extend alignment on annotated de Bruijn graphs
Bioinformatics, 40(Suppl 1):i337–i346, 2024. DOI: 10.1093/bioinformatics/btae226
H. Mustafa; M. Karasikov; N. Mansouri Ghiasi; G. Rätsch; A. Kahles
Why it matters: Label‑consistent SCA/MLA alignment used as MetaGraph's sensitive mode for experiment discovery.
OA: PMCID: PMC11211850
Aligning distant sequences to graphs using long seed sketches
Genome Research, 33(7):1208–1217, 2023. DOI: 10.1101/gr.277659.123
A. Joudaki; A. Meterez; H. Mustafa; R. Groot Koerkamp; A. Kahles; G. Rätsch
Why it matters: Long inexact sketch‑based seeding (MG‑Sketch) boosts recall at high divergence; complements MetaGraph's alignment toolkit.
OA: PMCID: PMC10538362

Database sources

The indexes searched here are built from public data resources. If your results draw on one of these databases, please cite its underlying source in addition to the MetaGraph paper above.

NCBI Sequence Read Archive (SRA)
sra-microbesra-metagutsra-fungisra-humansra-metazoasra-metazoa1ksra-mus_muculussra-plantssra-logan-chunkssra-logan-chunks-pex1sra-logan-chunks-pex2sra-logan-chunks-labatb
- The Sequence Read Archive
  Nucleic Acids Research, 39:D19–D21, 2011. DOI: 10.1093/nar/gkq1019
  R. Leinonen, et al.
Logan (SRA contigs)
sra-logan-chunkssra-logan-chunks-pex1sra-logan-chunks-pex2sra-logan-chunks-lab
- Logan: Planetary-Scale Genome Assembly Surveys Life's Diversity
  bioRxiv, 2024. DOI: 10.1101/2024.07.30.605881
  R. Chikhi, et al.
MetaSUB
metasub19metasub41
- A global metagenomic map of urban microbiomes and antimicrobial resistance
  Cell, 184:3376–3393.e17, 2021. DOI: 10.1016/j.cell.2021.05.002
  D. Danko, et al.
AllTheBacteria
atb
- AllTheBacteria: a community resource empowers biology and discovers novel peptide antibiotics
  bioRxiv, 2024. DOI: 10.1101/2024.03.08.584059
  M. Hunt, et al.
RefSeq
refseq33mrefseq85_coord
- Reference sequence (RefSeq) database at NCBI: current status, taxonomic expansion, and functional annotation
  Nucleic Acids Research, 44:D733–D745, 2016. DOI: 10.1093/nar/gkv1189
  N. A. O'Leary, et al.
UHGG (Unified Human Gastrointestinal Genome)
uhgguhgg_all
- A unified catalog of 204,938 reference genomes from the human gut microbiome
  Nature Biotechnology, 39:105–114, 2021. DOI: 10.1038/s41587-020-0603-3
  A. Almeida, et al.
Tara Oceans
tara-oceanstara-assemblies
- Structure and function of the global ocean microbiome
  Science, 348:1261359, 2015. DOI: 10.1126/science.1261359
  S. Sunagawa, et al.
gnomAD
gnomad
- A genomic mutational constraint map using variation in 76,156 human genomes
  Nature, 625:92–100, 2024. DOI: 10.1038/s41586-023-06045-0
  S. Chen, et al.
UniParc / UniProt
uniparc
- UniProt: the Universal Protein Knowledgebase in 2023
  Nucleic Acids Research, 51:D523–D531, 2023. DOI: 10.1093/nar/gkac1052
  The UniProt Consortium