search

lh3 / minigraph

Sequence-to-graph mapper and graph generator
https://lh3.github.io/minigraph
MIT License
417 stars 38 forks source link
bioinformatics genome-graph genomics pan-genome sequence-alignment

readme

Getting Started

git clone https://github.com/lh3/minigraph
cd minigraph && make
# Map sequence to sequence, similar to minimap2 without base alignment
./minigraph test/MT-human.fa test/MT-orangA.fa > out.paf
# Map sequence to graph
./minigraph test/MT.gfa test/MT-orangA.fa > out.gaf
# Incremental graph generation (-l10k necessary for this toy example)
./minigraph -cxggs -l10k test/MT.gfa test/MT-chimp.fa test/MT-orangA.fa > out.gfa
# Call per-sample path in each bubble/variation (-c not needed for this)
./minigraph -xasm -l10k --call test/MT.gfa test/MT-orangA.fa > orangA.call.bed

# Extract localized structural variations
gfatools bubble out.gfa > SV.bed

# Generate human MHC graph and call SVs jointly (~10 min)
curl -sL https://zenodo.org/record/8245267/files/mg-cookbook-v1_x64-linux.tar.bz2?download=1 | tar -jxf -
cd mg-cookbook-v1_x64-linux && ./00run.sh

Table of Contents

Introduction

Minigraph is a sequence-to-graph mapper and graph constructor. For graph generation, it aligns a query sequence against a sequence graph and incrementally augments an existing graph with long query subsequences diverged from the graph. The figure on the right briefly explains the procedure.

Minigraph borrows ideas and code from minimap2. It is fairly efficient and can construct a graph from 90 human assemblies in a couple of days using 24 CPU cores. Older versions of minigraph was unable to produce base alignment. The latest version can. Please add option -c for graph generation as it generally improves the quality of graphs.

Users' Guide

Installation

To install minigraph, type make in the source code directory. The only non-standard dependency is zlib. For better performance, it is recommended to compile with recent compliers.

Sequence-to-graph mapping

To map sequences against a graph, you should prepare the graph in the GFA format, or preferrably the rGFA format. If you don't have a graph, you can generate a graph from multiple samples (see the Graph generation section below). The typical command line for mapping is

minigraph -cx lr graph.gfa query.fa > out.gaf

You may choose the right preset option -x according to input. Minigraph output mappings in the GAF format, which is a strict superset of the PAF format. The only visual difference between GAF and PAF is that the 6th column in GAF may encode a graph path like >MT_human:0-4001<MT_orang:3426-3927 instead of a contig/chromosome name.

The minigraph GFA parser seamlessly parses FASTA and converts it to GFA internally, so you can also provide sequences in FASTA as the reference. In this case, minigraph will behave like minimap2, though likely producing different alignments due to differences between the two implementations.

Graph generation

The following command-line generates a graph in rGFA:

minigraph -cxggs -t16 ref.fa sample1.fa sample2.fa > out.gfa

which is equivalent to

minigraph -cxggs -t16 ref.fa sample1.fa > sample1.gfa
minigraph -cxggs -t16 sample1.gfa sample2.fa > out.gfa

File ref.fa is typically the reference genome (e.g. GRCh38 for human). It can also be replaced by a graph in rGFA. Minigraph assumes sample1.fa to be the whole-genome assembly of an individual. This is an important assumption: minigraph only considers 1-to-1 orthogonal regions between the graph and the individual FASTA. If you use raw reads or put multiple individual genomes in one file, minigraph will filter out most alignments as they cover the input graph multiple times.

The output rGFA can be converted to a FASTA file with gfatools:

gfatools gfa2fa -s graph.gfa > out.stable.fa

The output out.stable.fa will always include the initial reference ref.fa and may additionally add new segments diverged from the initial reference.

Calling structural variations

A minigraph graph is composed of chains of bubbles with the reference as the backbone. Each bubble represents a structural variation. It can be multi-allelic if there are multiple paths through the bubble. You can extract these bubbles with

gfatools bubble graph.gfa > var.bed

The output is a BED-like file. The first three columns give the position of a bubble/variation and the rest of columns are:

Given an assembly, you can find the path/allele of this assembly in each bubble with

minigraph -cxasm --call -t16 graph.gfa sample-asm.fa > sample.bed

On each line in the BED-like output, the last colon separated field gives the alignment path through the bubble, the path length in the graph, the mapping strand of sample contig, the contig name, the approximate contig start and contig end. The number of lines in the file is the same as the number of lines in the output of gfatools bubble.

SV calling showcase (human MHC)

The following example generates a graph for 61 humam MHC haplotypes and calls SVs from them. Primary sequences are retrieved from an AGC archive.

# Obtain cookbook data and precompiled binaries
curl -sL https://zenodo.org/record/8245267/files/mg-cookbook-v1_x64-linux.tar.bz2?download=1 | tar -jxf -
cd mg-cookbook-v1_x64-linux

# Generate graph. This takes ~7 minutes.
./agc listset MHC-61.agc | awk '!/GRC/{a=a" <(./agc getset MHC-61.agc "$1")"}END{print "./minigraph -cxggs <(./agc getset MHC-61.agc MHC-00GRCh38)"a}' | bash > MHC-61.gfa 2> MHC-61.gfa.log

# Call SVs per sample. This takes a couple of minutes.
./agc listset MHC-61.agc | xargs -i echo ./minigraph -cxasm --call -t1 MHC-61.gfa '<(./agc getset MHC-61.agc {})' \> {}.bed 2\> {}.bed.log | parallel -j16

# Merge per-sample calls and generate VCF. `-r0` indicates the reference sample.
paste *.bed | ./k8 mgutils.js merge -s <(./agc listset MHC-61.agc) - | gzip > MHC-61.sv.bed.gz
./k8 mgutils-es6.js merge2vcf -r0 MHC-61.sv.bed.gz > MHC-61.sv.vcf

In this example, the GRCh38 haplotype is named "MHC-00GRCh38" in the AGC archive and is taken as the reference. The awk command line generates a command line that retrieves each haplotype on the fly and feeds it to minigraph. misc/mgutils.js merge combines per-sample calls and generates a merged BED file. The final misc/mgutils-es6.js merge2vcf derives a VCF file. This script requires the latest k8 JavaScript runtime.

Prebuilt graphs

Prebuilt human graphs in the rGFA format can be found at Zenodo.

Algorithm overview

In the following, minigraph command line options have a dash ahead and are highlighted in bold. The description may help to tune minigraph parameters.

  1. Read all reference bases, extract (-k,-w)-minimizers and index them in a hash table.

  2. Read -K [=500M] query bases in the mapping mode, or read all query bases in the graph construction mode. For each query sequence, do step 3 through 5:

  3. Find colinear minimizer chains using the minimap2 algorithm, assuming segments in the graph are disconnected. These are called linear chains.

  4. Perform another round of chaining, taking each linear chain as an anchor. For a pair of linear chains, minigraph tries to connect them by doing graph wavefront alignment algorithm (GWFA). If minigraph fails to find an alignment within an edit distance threshold, it will find up to 15 shortest paths between the two linear chains and chooses the path of length closest to the distance on the query sequence. Chains found at this step are called graph chains.

  5. Identify primary chains and estimate mapping quality with a method similar to the one used in minimap2. Perform base alignment.

  6. In the graph construction mode, collect all mappings longer than -d [=10k] and keep their query and graph segment intervals in two lists, respectively.

  7. For each mapping longer than -l [=100k], finds poorly aligned regions. A region is filtered if it overlaps two or more intervals collected at step 6.

  8. Insert the remaining poorly aligned regions into the input graph. This constructs a new graph.

Limitations