Rapid, accurate long- and short-read mapping to large pangenome graphs with vg Giraffe

Rapid, accurate long- and short-read mapping to large pangenome graphs with vg Giraffe | bioRxiv /* */ /* */ <!-- <!-- /*! * yepnope1.5.4 * (c) WTFPL, GPLv2 */ (function(a,b,c){function d(a){return"[object Function]"==o.call(a)}function e(a){return"string"==typeof a}function f(){}function g(a){return!a||"loaded"==a||"complete"==a||"uninitialized"==a}function h(){var a=p.shift();q=1,a?a.t?m(function(){("c"==a.t?B.injectCss:B.injectJs)(a.s,0,a.a,a.x,a.e,1)},0):(a(),h()):q=0}function i(a,c,d,e,f,i,j){function k(b){if(!o&&g(l.readyState)&&(u.r=o=1,!q&&h(),l.onload=l.onreadystatechange=null,b)){"img"!=a&&m(function(){t.removeChild(l)},50);for(var d in y[c])y[c].hasOwnProperty(d)&&y[c][d].onload()}}var j=j||B.errorTimeout,l=b.createElement(a),o=0,r=0,u={t:d,s:c,e:f,a:i,x:j};1===y[c]&&(r=1,y[c]=[]),"object"==a?l.data=c:(l.src=c,l.type=a),l.width=l.height="0",l.onerror=l.onload=l.onreadystatechange=function(){k.call(this,r)},p.splice(e,0,u),"img"!=a&&(r||2===y[c]?(t.insertBefore(l,s?null:n),m(k,j)):y[c].push(l))}function j(a,b,c,d,f){return q=0,b=b||"j",e(a)?i("c"==b?v:u,a,b,this.i++,c,d,f):(p.splice(this.i++,0,a),1==p.length&&h()),this}function k(){var a=B;return a.loader={load:j,i:0},a}var l=b.documentElement,m=a.setTimeout,n=b.getElementsByTagName("script")[0],o={}.toString,p=[],q=0,r="MozAppearance"in l.style,s=r&&!!b.createRange().compareNode,t=s?l:n.parentNode,l=a.opera&&"[object Opera]"==o.call(a.opera),l=!!b.attachEvent&&!l,u=r?"object":l?"script":"img",v=l?"script":u,w=Array.isArray||function(a){return"[object Array]"==o.call(a)},x=[],y={},z={timeout:function(a,b){return b.length&&(a.timeout=b[0]),a}},A,B;B=function(a){function b(a){var a=a.split("!"),b=x.length,c=a.pop(),d=a.length,c={url:c,origUrl:c,prefixes:a},e,f,g;for(f=0;f<d;f++)g=a[f].split("="),(e=z[g.shift()])&&(c=e(c,g));for(f=0;f<b;f++)c=x[f](c);return c}function g(a,e,f,g,h){var i=b(a),j=i.autoCallback;i.url.split(".").pop().split("?").shift(),i.bypass||(e&&(e=d(e)?e:e[a]||e[g]||e[a.split("/").pop().split("?")[0]]),i.instead?i.instead(a,e,f,g,h):(y[i.url]?i.noexec=!0:y[i.url]=1,f.load(i.url,i.forceCSS||!i.forceJS&&"css"==i.url.split(".").pop().split("?").shift()?"c":c,i.noexec,i.attrs,i.timeout),(d(e)||d(j))&&f.load(function(){k(),e&&e(i.origUrl,h,g),j&&j(i.origUrl,h,g),y[i.url]=2})))}function h(a,b){function c(a,c){if(a){if(e(a))c||(j=function(){var a=[].slice.call(arguments);k.apply(this,a),l()}),g(a,j,b,0,h);else if(Object(a)===a)for(n in m=function(){var b=0,c;for(c in a)a.hasOwnProperty(c)&&b++;return b}(),a)a.hasOwnProperty(n)&&(!c&&!--m&&(d(j)?j=function(){var a=[].slice.call(arguments);k.apply(this,a),l()}:j[n]=function(a){return function(){var b=[].slice.call(arguments);a&&a.apply(this,b),l()}}(k[n])),g(a[n],j,b,n,h))}else!c&&l()}var h=!!a.test,i=a.load||a.both,j=a.callback||f,k=j,l=a.complete||f,m,n;c(h?a.yep:a.nope,!!i),i&&c(i)}var i,j,l=this.yepnope.loader;if(e(a))g(a,0,l,0);else if(w(a))for(i=0;i (function(w,d,s,l,i){w[l]=w[l]||[];w[l].push({'gtm.start':new Date().getTime(),event:'gtm.js'});var f=d.getElementsByTagName(s)[0];var j=d.createElement(s);var dl=l!='dataLayer'?'&l='+l:'';j.src='//www.googletagmanager.com/gtm.js?id='+i+dl;j.type='text/javascript';j.async=true;f.parentNode.insertBefore(j,f);})(window,document,'script','dataLayer','GTM-M677548'); Skip to main content Home About Submit ALERTS / RSS Search for this keyword Advanced Search New Results Rapid, accurate long- and short-read mapping to large pangenome graphs with vg Giraffe View ORCID Profile Xian Chang , View ORCID Profile Adam M. Novak , View ORCID Profile Jordan M. Eizenga , View ORCID Profile Jouni Sirén , View ORCID Profile Jean Monlong , View ORCID Profile Shloka Negi , View ORCID Profile Francesco Andreace , View ORCID Profile Sagorika Nag , View ORCID Profile Konstantinos Kyriakidis , View ORCID Profile Glenn Hickey , View ORCID Profile Stephen Hwang , View ORCID Profile Emmanuèle C. Délot , View ORCID Profile Andrew Carroll , View ORCID Profile Kishwar Shafin , View ORCID Profile Pi-Chuan Chang , View ORCID Profile Faith Okamoto , View ORCID Profile Benedict Paten , the Human Pangenome Reference Consortium doi: https://doi.org/10.1101/2025.09.29.678807 Xian Chang 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA 2 Université de Toulouse, INRAE , UR 875 MIAT, Castanet-Tolosan, France Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Xian Chang For correspondence: bpaten{at}ucsc.edu xian-hui.chang{at}inrae.fr Adam M. Novak 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Adam M. Novak Jordan M. Eizenga 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Jordan M. Eizenga Jouni Sirén 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Jouni Sirén Jean Monlong 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA 3 Institut de Recherche en Santé Digestive, Université de Toulouse , INSERM, INRA, ENVT, UPS, Toulouse, France Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Jean Monlong Shloka Negi 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Shloka Negi Francesco Andreace 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA 4 Institut Pasteur, Université Paris Cité, Sequence Bioinformatics Unit , F-75015 Paris, France Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Francesco Andreace Sagorika Nag 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Sagorika Nag Konstantinos Kyriakidis 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Konstantinos Kyriakidis Glenn Hickey 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Glenn Hickey Stephen Hwang 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA 5 XDBio Program, Johns Hopkins University , Baltimore, MD, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Stephen Hwang Emmanuèle C. Délot 6 Institute for Clinical and Translational Science, University of California , Irvine, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Emmanuèle C. Délot Andrew Carroll 7 Google Inc , Mountain View, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Andrew Carroll Kishwar Shafin 7 Google Inc , Mountain View, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Kishwar Shafin Pi-Chuan Chang 7 Google Inc , Mountain View, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Pi-Chuan Chang Faith Okamoto 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Faith Okamoto Benedict Paten 1 UC Santa Cruz Genomics Institute , Santa Cruz, CA, USA Find this author on Google Scholar Find this author on PubMed Search for this author on this site ORCID record for Benedict Paten For correspondence: bpaten{at}ucsc.edu xian-hui.chang{at}inrae.fr Abstract Full Text Info/History Metrics Supplementary material Preview PDF 1 Abstract We previously introduced Giraffe, a short-read-to-pangenome graph mapper available in the vg pangenomics toolkit. Giraffe was fast and accurate for mapping short reads to human-scale pangenomes, but struggled with long reads. Long reads present a unique challenge to pangenome mapping algorithms due to their length and error profile, which allow them to take more topologically complex paths through the pangenome graph and increase the possible search space for the algorithm. We present updates to Giraffe that allow it to quickly and accurately map long reads to pangenome graphs. For both short and long reads, Giraffe mapping to a pangenome containing data from more than 450 human haplotypes, generated by the Human Pangenome Reference Consortium, is comparable in speed to linear mappers to human reference genomes; Giraffe is also over an order of magnitude faster than GraphAligner, the current state-of-the-art long-read-to-pangenome mapper. Its alignments produce similar or improved small and structural variant calling results, compared to those from commonly used graph-based and linear mappers. We additionally demonstrate using Giraffe’s long read alignments in a pangenome-guided assembly workflow, which is capable of producing more contiguous local assemblies than Hifiasm in our test regions. 2 Introduction Pangenomes are emerging as a promising alternative to the standard single linear reference genome, because they are capable of representing the genetic diversity present in a population [ 1 , 2 ]. There have been several recent efforts to establish human reference pangenomes, either targeted (at particular countries [ 3 ], ancestries [ 4 ], or sets of ethnicities [ 5 ]), or global across the human population [ 6 ]. Pangenomes are commonly represented as variation graphs, where nodes represent nucleotide sequences, edges represent adjacencies between sequences, and paths through the graph represent the original haplotype sequences of the pangenome [ 7 ]. These graph structures are an efficient representation of pangenomes, but the complex topology of graphs makes them more difficult to work with than linear reference genomes, especially as the graphs grow in sequence content and genetic diversity. In particular, mapping sequencing reads, a critical first step for many common bioinformatics pipelines, requires specialized data structures and algorithms to deal efficiently with a graph reference. Read mappers that align to a standard linear reference [ 8 , 9 , 10 ] commonly use a seed-and-extend approach [ 11 ]. Short seed alignments are found using an index of the reference genome. Many algorithms then partition seeds into groups that are likely to have come from the same alignment to the reference. Seeds are then extended into the full base-level alignment using dynamic programming. Existing graph mappers use versions of these basic components that have been adapted to a graph context. Early graph alignment algorithms were designed to align reads to partial order alignment (POA) graphs that themselves represent multiple sequence alignments [ 12 ]. These POA aligners generalized standard dynamic programming algorithms to align to acyclic graphs [ 12 , 13 ]. The original vg map algorithm further extended the POA algorithm to cyclic graphs by “unrolling” the graph to remove cycles, then applying POA to implement its extension step [ 7 ]. GraphAligner, currently the only practical tool for mapping long reads to arbitrary graphs, generalizes the linear Shift-And exact string matching algorithm [ 14 ] for its seeding step, and Myers’ bitvector alignment algorithm [ 15 ] for its extension step, to align to cyclic graphs [ 16 ]. The original short read Giraffe relied on embedded haplotype sequences to map to the graph [ 17 ]. This set of embedded haplotypes could first be personalized using haplotype sampling , to remove local haplotypes not relevant to a particular sample [ 18 ]. Next, seeds were found by using a minimizer index over the haplotypes, and clustered by using a distance index to find minimum graph distances. Seeds within promising clusters were gaplessly extended along the haplotypes, and finally the extension was completed using dynamic programming against the graph. Due to the fast gapless extension step, in which the entire alignment was usually found, Giraffe was very fast for short reads [ 17 ]. However, being designed for short reads, where gaps are rare and a read will usually follow a single known haplotype for its entire length, Giraffe quickly overwhelmed our computational resources when applied to long reads. Long reads are another rapidly growing technology with great potential to improve genomic analyses. Currently, High Fidelity (HiFi) reads from Pacific Biosciences have lengths between 10 and 25 kbp and accuracy of up to 99.95% [ 19 , 20 ]. The most recent R10 chemistry from Oxford Nanopore Technologies achieves read lengths on the order of 10-100 kbp, with ultra-long reads achieving lengths up to 882 kbp [ 21 ], and accuracy of over 99% [ 22 , 23 ]. Because of their increased length, these technologies are useful for resolving complex and large structural variants, and for identifying long-range linkages between alleles. Both HiFi and R10 sequencing technologies have gained widespread use in large-scale genomics projects [ 24 , 25 ] due to this improved resolution ability, as well as their lowering cost and high throughput. Despite the growing popularity of both pangenomes and long reads, there are currently few tools for mapping long reads to pangenomes. The length and error profile of the reads makes every stage of a mapping algorithm more difficult. Gapped alignment is a particularly challenging problem with long reads: even in a linear context, long reads can produce dynamic programming matrices that are unmanageably large. The problem becomes even harder in a graph context, as aligners must also navigate potentially large and complex graph topologies. To deal with the increased difficulty of mapping long reads, many tools [ 10 , 26 , 27 , 28 ] build on the seed-and-extend approach by adopting a seed-and-chain or seed-chain-extend strategy [ 11 ]. After seeds are found, and before they are extended into alignments, chains of co-linear seeds are identified. Then, extension consists of smaller alignment problems between consecutive seeds in a chain. Chaining requires an ordering and a distance metric between seeds, both of which are ambiguous and more expensive to compute in a graph. Chaining is particularly difficult in graphs that contain cycles, as a node may occur before or after itself or any other node in the cycle [ 29 , 28 , 30 ]. Existing graph chaining algorithms use distance calculations based on linear approximations of the graph. Some tools [ 29 , 28 , 31 ] are based on an algorithm from Mäkinen et al. [ 30 ] that uses a minimum path cover of the graph to determine reachability and distance. Other tools might enumerate shortest-length walks between graph positions (Minigraph [ 26 ]) or estimate linear distances based on chains in the snarl decomposition (GraphAligner [ 32 ]). As a result of these different heuristics for overcoming the challenges of long read-to-pangenome mapping, different mappers have different advantages and limitations. GraphAligner, for example, can accurately map reads to arbitrary graphs, but it is slow, particularly as the complexity of the graph increases [ 32 ]. Minigraph [ 26 ], which was originally designed to map assemblies to graphs containing only structural variants (SVs), struggles to map to graphs containing small insertions or deletions (indels) or single nucleotide variants (SNVs). PanAligner [ 27 ] uses its own graph chaining algorithm with components from Minigraph, and GraphChainer [ 28 ] uses its own graph chaining algorithm with components from GraphAligner. Minichain uses a haplotype-aware chaining algorithm that prioritizes alignments that remain on the same haplotype [ 31 ]. PanAligner has the same limitations as Minigraph and was an order of magnitude slower than GraphAligner in our initial tests. GraphChainer and Minichain can only map to graphs without cycles. We present an updated version of Giraffe capable of mapping both long and short reads. The long read Giraffe algorithm uses a seed-chain-extend framework, using a novel data structure for computing distances for chaining. We show that Giraffe is among the fastest graph-based or linear read mappers, while still being competitive in mapping accuracy and downstream variant calling results. Finally, we use Giraffe’s long read mappings in a haplotype-resolved pangenome-guided assembly workflow for assembling a specific region of interest, solving a relaxed version of the haplotype-resolved de novo assembly problem addressed by tools like Hifiasm [ 33 ]. 3 Results 3.1 Long read Giraffe algorithm overview The long read Giraffe algorithm is adapted from the original short read Giraffe algorithm [ 17 ] to efficiently deal with the longer sequence and higher error rate of long reads ( Figure 1 ). The seed-and-extend short read algorithm has been expanded into a seed-chain-extend algorithm of the kind typical of long read mappers [ 11 ], with additional improvements that are useful in a long read context. For seeding, the long read algorithm uses weighted minimizer seeds, which prioritizes seeds with fewer hits in the graph ( Figure 1 C ). For chaining, we address the challenges of complex graph topology using a novel data structure for finding graph-distances between seeds that are supported by the corresponding read-distances ( Figure 1 D ). Using this data structure, the algorithm computes co-linear chains of seeds that occur in the same order in the read and graph, which form the backbone of the final alignment ( Figure 1 E ). Finally, for extension, base-level alignment is done in between consecutive seeds in the chain using alignment algorithms that limit the problem to alignment either against linear haplotypes or within smaller bands of the alignment matrix ( Figure 1 F ). Download figure Open in new tab Figure 1: Overview of the long read Giraffe algorithm. (A) The inputs to the algorithm: the query read and the reference variation graph. (B) The variation graph with its corresponding snarl tree. Rectangles in the snarl tree represent chains and ovals represent snarls. Chains on the snarl tree are colored according to their node children. Nodes are not shown on the snarl tree. (C) Seeds are found using a minimizer index. Arrows on the read and reference graph represent seed alignments. (D) A zip code tree is constructed to represent the connectivity between seeds on the graph using snarl tree relationships. Nodes in the zip code tree represent either a seed on the graph, or the boundary of a snarl or chain containing a seed. The nodes are ordered according to a pre-and-post-order traversal of the snarl tree. Edges connect adjacent seeds and boundaries, and are labeled with minimum distances from the variation graph. Distances between seeds in the graph can be calculated in a traversal of the zip code tree. (E) Co-linear chaining is done by dynamic programming over the seeds to maximize the coverage over the read and minimize the gap cost of consecutive seeds. The cost of a gap between seeds is found using read distances from the read and graph distances from a traversal of the zip code tree. (F) Base-level alignment is done between adjacent seeds in a chain, and out from the first and last seeds to produce the full-length alignment. 3.2 Experiment setup: graphs, reads, and mappers We compared Giraffe to a variety of linear mappers aligning to the CHM13 reference genome, and to graph mappers aligning to graphs constructed from the Human Pangenome Reference Consortium’s (HPRC) release 2 assemblies (Section S5.1). We used the HPRC graph constructed with just Minigraph (HPRC-Minigraph) as well as the graph constructed with the Minigraph-Cactus pipeline with allele frequency filtering (HPRC-d46) [ 6 ]. In a previous study [ 18 ], we found that short read Giraffe performed better when using personalized pangenome graphs (see 2). We therefore tested Giraffe on graphs that were haplotype-sampled to contain only 16 haplotypes and whichever of the two linear references was appropriate (HPRC-Sampled16). The haplotype sampled graph used a base graph constructed with the Minigraph-Cactus pipeline with selective clipping (HPRC-clipped). Our haplotype-sampling pipeline requires k-mers from a whole-genome read set, so we generated a different sampled graph for each sample and sequencing technology, by using an appropriate set of real reads (Section S5.1). Finally, we also used Giraffe to map to a negative control variation graph containing only CHM13 (also referred to as CHM13). We mapped real datasets of long read technologies (HiFi and R10) and short read technologies (Illumina and Element) reads (Section S5.2). We compared Giraffe to Minimap2 [ 10 ], Winnowmap [ 34 ], GraphAligner [ 16 , 32 ], and Minigraph [ 26 ] for mapping HiFi and R10 reads; PBMM2 [ 10 , 35 ] for mapping HiFi reads; and to Minimap2 and BWA-MEM [ 9 ] for mapping Illumina and Element reads (Section S5.3). Giraffe was run using the long read algorithm on HiFi and R10 reads, and using the paired-end short read algorithm for Illumina and Element reads. GraphAligner was run using the default parameters on simulated reads and when aligning to the HPRC-Minigraph graph with R10 reads, but we were unable to finish mapping real HiFi or R10 reads to the HPRC-d46 graph, or real HiFi reads to the HPRC-Minigraph graph, within the seven-day time limit of our servers, so this was done using a parameter set recommended by the developer to optimize for speed, which we call the “fast” parameters (Section S5.3). 3.3 Mapping evaluation We used simulated read datasets to evaluate mapper performance on HiFi, R10, Illumina, and Element reads. Each dataset contained 1 million reads simulated to match the error profiles of the real datasets (Section S5.2). Giraffe’s accuracy was similar to that of other mappers, and it had the highest true positive rate for HiFi reads when mapping to the allele frequency-filtered HPRC-d46 graph ( Figure 2 , Tables S1-S4). Giraffe generally had better mapping quality calibration than other mappers (Figure S4) and the fewest incorrectly mapped reads with a mapping quality (MAPQ) of 60, meaning that it was less likely to overestimate its accuracy. (Tables S1-S4). Download figure Open in new tab Figure 2: Mapping accuracy on simulated reads. ROC plots for one million reads simulated to resemble HiFi (A), R10 (B), Illumina (C), and Element (D) reads, zoomed in to show the separation of the curves. The results are stratified by mapping quality; the size of each point represents the log-scaled number of reads with the given mapping quality. X-axes are log-scaled. Linear mappers (Minimap2, PBMM2, Winnowmap, BWA-MEM) were used to align to CHM13, Giraffe to the linear CHM13 graph, and graph mappers (Giraffe, GraphAligner, Minigraph) to the HPRC-d46 graph (Giraffe and GraphAligner), HPRC-Minigraph graph (Minigraph), and the HPRC-Sampled16 graph (Giraffe). We also mapped real read sets for each sequencing technology (Section S5.2), to evaluate unaligned bases, and to assess speed and memory use. Because GraphAligner exceeded the seven-day time limit of our servers in some cases, we re-ran it using a parameter set recommended by the developer (Section S5.3). We evaluated the base-level alignments of real long reads by comparing the total number of different types of unaligned bases (soft-clipped, hard-clipped, and unmapped) that each mapper produced; for short reads, we looked at the fraction of unmapped bases ( Figure 3 ). For long reads, again, results were similar between Giraffe and most other mappers. For short reads, we found that the existing short read Giraffe algorithm could leave noticeably more reads unmapped than other mappers. We noted the same pattern of unmapped reads when mapping simulated reads. Of the simulated reads that Giraffe left un-mapped, all were incorrectly mapped by BWA-MEM and Minimap2. Download figure Open in new tab Figure 3: Unaligned bases. Bar plots of the percent of base pairs that were unaligned due to being softclipped, hardclipped, or in reads that were left unmapped, in real HiFi (A) and R10 (B) reads, and the percent of bases that were unmapped in Illumina (C) and Element (D) reads. Bases that were unaligned due to being in unmapped reads are represented by the lower, darker portion of each bar in (A) and (B), and are the entirety of each bar in (C) and (D). Giraffe was about an order of magnitude faster than GraphAligner’s fast mode ( Figure 4 ). Giraffe’s speed and memory use varied with the complexity of the reference graph it aligned to, with the simplest CHM13 graph being the fastest and lowest memory and the most complex HPRC graphs (HPRC-d46 and HPRC-Sampled16) being the slowest with the biggest memory footprint ( Figure 4 ). Download figure Open in new tab Figure 4: Runtime and memory use. Runtime (A, B, C, and D) and memory use (E, F, G, and H) of each mapper on real PacBio HiFi (A and E), Oxford Nanopore R10 (B and F), Illumina (C and G), and Element (D and H) reads. The lower, darker portion of each runtime bar shows the part of the runtime used for loading and building indexes, as reported by each mapper, including the time for haplotype sampling for Giraffe. * GraphAligner exceeded the 7-day time limit of our servers when run with the default settings on HiFi and R10 reads on the HPRC-d46 graph, and on HiFi reads on the HPRC-Minigraph graph. It was re-run using a parameter set (GraphAligner-fast) that was provided by the developer (Section S5.3). 3.2 Small variant calling with DeepVariant To more robustly assess the quality of Giraffe’s long read alignments, we compared the performance of DeepVariant [ 36 ] using reads mapped with Giraffe and Minimap2. For Giraffe, PacBio and R10 reads from the HPRC (for HG002) were mapped to the HPRC-d46 graph and the haplotype-sampled HPRC-Sampled16 graph, then surjected onto CHM13. For Minimap2, these reads were mapped directly to CHM13 (see Section S5.3). Variant calling was done for both mappers using the ONT R104 model of DeepVariant for R10 reads, and the PACBIO model for HiFi reads mapped with Minimap2. For HiFi reads mapped with Giraffe, we used a custom model trained on reads mapped by Giraffe (see Section S5.4.1). Calling accuracy was evaluated using hap.py version 0.3.15 [ 37 ] against the Genome in a Bottle (GIAB) 4.2.1 truth set [ 38 , 39 ]. We did not assess short read variant calling accuracy because this has been tested extensively [ 17 , 18 , 40 ] and has not changed with the new release of Giraffe. Giraffe generally had slightly higher precision, recall, and F1 scores than Minimap2, with the haplotype sampling pipeline providing further improvements ( Figure 5 A-D ). Download figure Open in new tab Figure 5: Variant calling and genotyping. SNPs (A and B) and indels (C and D) were called using DeepVariant with HiFi (A and C) and R10 (B and D) reads. SV genotyping was performed with Giraffe on the HPRC-d46 graph (Giraffe), Giraffe with a sampled graph with 16 haplotypes (Giraffe sampled), and GraphAligner’s fast mode on the HPRC-d46 graph, all with vg call. SV calling and genotyping was done using Minimap2 with Sniffles2. SV genotyping accuracy was compared for HiFi (E) and R10 (F) reads. Giraffe was used to map reads to the HPRC-d46 graph and to the HPRC-Sampled16 graph. Graphaligner’s fast mode was used to map reads to the HPRC-d46 graph. Minimap2 was used to map reads to CHM13. Download figure Open in new tab Figure 6: Pangenome-guided assembly workflow and application to rare disease cases. 3.5 Structural variant genotyping with vg call We assessed the performance of Giraffe on structural variant genotyping with vg call using a pipeline based on Hickey et al. [ 41 ] (Section S5.5). vg call was run on Giraffe’s mappings to either the HPRC-d46 graph or the HPRC-Sampled16 graph. SV genotyping in each condition used the same graph that was used for mapping, except that for the HPRC-Sampled16 graph, a version was used with with both linear references included. We compared these two Giraffe conditions against two competitors: vg call on GraphAligner’s fast mode alignments to the HPRC-d46 graph, and the linear SV caller and genotyper Sniffles2 [ 42 , 43 ] on Minimap2’s alignments to the CHM13 linear reference. Genotyping results were evaluated against the Genome in a Bottle Consortium’s T2T Q100 HG002 truth set [ 44 ] using Truvari [ 45 ] (Section S5.5). Despite being restricted to only the variants present in the graph, the Giraffe-and- vg call pipeline with the haplotype-sampled graph performed comparably with Minimap2-and-Sniffles2, with the highest recall of any of the methods tested and a higher F1 score that Minimap2-and-Sniffles2 for R10 reads ( Figure 5 E and F , Tables S13, S14). 3.6 Validation and application of pangenome-guided assembly for complex regions We developed a prototype pangenome-guided assembler (PGA) (see Section 5.3) that leverages long read Giraffe alignments for targeted regional assembly. Briefly, Giraffe is used to map long reads to a pangenome. Sites of variation within the pangenome graph, termed bubbles or snarls, are used to determine haplotypic anchors in the reads, and then these anchors and their connections in the reads are used to create a phased genome assembly. Using the anchors derived from common variant sites, the assembly process is able to assemble a sample’s haplotype sequences, including private variations not present in the mapped-to pangenome. We initially evaluated its performance using HG002 R10 reads (Section S6.1), across six selected loci: three structurally simple regions (CHR13-1Mb, CHR8-700kb, CHR2-600kb) and three complex, medically relevant regions with segmental duplications (RCCX, PDPK, GOLGA8). For all six regions, PGA produced accurate phased assemblies (Figures S5S10). For comparison, we generated a complete Hifiasm assembly of the sample, aligned it to the HG002v1.0.1 reference with Minimap2, and retrieved the contigs overlapping the target region, trimming them to the aligned segments for evaluation. The evaluation showed comparable mismatch rates between both assemblies, even though PGA does not perform explicit read correction. In certain cases (Figures S6, S8), PGA produced better assembly contiguity than Hifiasm. Following validation using the HG002 benchmark sample, we applied PGA to assemble the complex RCCX locus (Section S6.2) in two Congenital Adrenal Hyperplasia (CAH) cases, who had been analyzed in a previous study published by our group ([ 46 , 47 ]), and compared the assemblies to those from a specialized method (Parakit) developed for analyzing this challenging locus [ 47 ]. With PGA, we were able to directly assemble the RCCX haplotypes for these two CAH probands (IDs DSDTRN09 and DSDTRN04 in Negi et al. [ 46 ]), and accurately detect the pathogenic compound heterozygous variants within these haplotype-resolved assemblies (Figure 6.2), recapitulating the earlier results made using Parakit and demonstrating accurate assembly of variants not found within the pangenome. 1. PGA workflow overview The inputs to the workflow are the reference variation graph and sample long reads. (A) Personalized pangenome construction using graph-unique k-mer classifications (faded node is not part of the personalized graph). (B) Reads are aligned to the personalized graph using long read Giraffe. (C) Read mappings at leaf snarls are used to generate anchors (potentially haplotype-informative k-mers enabling separation of reads). (D) The Shasta assembler constructs an anchor graph, with anchors as vertices and shared reads as edges. Its detangling algorithm traverses this graph to resolve haplotype paths and generate a phased assembly. 2. Resolving RCCX haplotypes in two probands For each proband, the figure displays PGA assemblies, sequencing statistics, the alignment profile of the phased haplotypes against an RCCX collapsed pangenome (using Parakit’s visualization), and the final RCCX haplotypes structure in sample. In the alignment profiles, when a haplotype traverses multiple RCCX modules (nodes: red = pseudogene-specific; green = gene-specific; blue = shared between SD modules) by looping through the pangenome, the different traversals are separated vertically and shown as multiple rows. The gene annotation track shows CYP21A2 and CYP21A1P annotations. Vertical dotted lines highlight variant positions across panels. (A) Proband DSDTRN09: Hap-1 alignment through the pseudogenes followed by the genes reveals HERV-K deletion in C4A and a gene-converted pathogenic Int2G SNV (red circle). Hap-2 contains a fusion located beyond the CYP21A2 gene in TNXB (blue triangle). (B) Proband DSDTRN04: Assembly alignment reveals a gene-converted pathogenic Q319X nonsense SNV (pink circle) in Hap-1 and a hybrid 5’-CYP21A1P/CYP21A2-3’ fusion in Hap-2. 4 Discussion As the field of pangenomics continues to expand, there is a growing need for efficient tools for working with increasingly large and complex pangenome graphs. The latest version of Giraffe, part of our vg toolkit, is now capable of mapping both short and long reads to graphs of varying complexity—including to graphs constructed from more than 450 haplotypes from the HPRC’s second release. For both short and long reads, Giraffe achieves similar read mapping, and overall slightly better variant calling accuracy, relative to existing best-of-breed linear and pangenome mappers, while being comparable in speed to the best linear mappers. Notably, Giraffe is over an order of magnitude faster than GraphAligner, the current state-of-the-art long read-to-pangenome mapper. To demonstrate the potential of long-read-to-pangenome mapping, we developed a prototype pangenome guided assembly pipeline. With this pipeline, we were able to produce local, complete, phased assemblies of targeted regions of the genome, including those containing highly similar segmental duplications, that were more contiguous than the assemblies produced by Hifiasm and comparably accurate. Assembling the RCCX loci from two patients, we were able to accurately recover complex haplotypes that contain structural variations not present in the pangenome. This is in contrast to existing methods for structural variant calling against a pangenome, like the vg call -based methods evaluated here, which generally require the variation to be known in advance. While further scaling and testing is required to convert this prototype assembler into a fully fledged tool, such a hybrid assembly process has great promise for future, efficient genome inference. It avoids the need for all-against-all read alignment (a step necessary during de novo assembly), and, by providing a strong prior for likely haplotypes, provides a framework that might facilitate more accurate assembly, particularly, we suspect, at lower sequencing coverages. We demonstrate Giraffe’s performance on human graphs containing cycles and both large and small variants, but it is still untested on the more complex graphs constructed with the PanGenome Graph Builder (PGGB) [ 48 ] and on more genetically diverse species. PGGB’s reference-free approach to graph building provides an unbiased view of the homology within and among genomes. However, due to the complex topology of the PGGB graphs, we have not been able to construct indexes for Giraffe, and to our knowledge there are no tools capable of mapping reads to these graphs. There remains a need for indexes and algorithms that can handle the large cycles and deeply-nested variants present in PGGB graphs; we are actively working to extend Giraffe in this direction. The construction of the graph being mapped to also has a profound effect on the downstream alignments and calling results. When graph alignments are projected back onto a linear reference, the base-level alignment of reads will often follow the alignment used to construct the graph. A pathological “spelling” of the graph’s alignment (for example, one providing multiple paths that spell the same sequence) may negatively affect downstream results, even if the read was mapped to the correct location and represents the correct sequence. We found ourselves obliged to work around this effect (see Section S4.2). We are actively pursuing new graph construction techniques that we think will allow for building graphs that produce graph alignments that in turn produce more useful linear alignments. We also suspect that there may be an opportunity here to revive the field of indel realignment, seemingly last popular in the era of GATK 3. We hypothesize that an indel realigner with long read support, ideally working in pangenome space, would improve point variant calling accuracy from pangenome alignments. Unfortunately, we know of no suitable existing tool. There is still work to be done to further improve the Giraffe algorithm. We currently use the original Giraffe algorithm for mapping paired-end short reads, but we expect results to improve when adding pairing support to the long read algorithm. Furthermore, while the improvements in variant calling demonstrated are currently modest, we believe that there is considerable room for further improvement. One future idea is to score recombinations, and so penalize read mappings that are haplotype inconsistent, as is often case when mapping reads to paralogs [ 31 ]. Such recombination awareness also opens the possibility to assign reads to local haplotypes and use these local haplotypes more directly in downstream applications. 5 Online Methods 5.1 Variation graphs and indexes Giraffe is implemented as part of the vg toolkit, which uses a variation graph model for representing pangenomes [ 7 ]. A variation graph is a bidirected graph in which nodes are labeled with nucleotide sequences, and edges represent possible adjacencies between these sequences. Nodes in a variation graph have two sides, which are arbitrarily designated as left and right . Edges connect pairs of node sides. Valid walks through the graph must enter and exit opposite sides of a node, so each node visit along the walk has an orientation. A forward (i.e. left to right) traversal of a node represents the forward sequence of the nucleotides, whereas a backwards traversal represents its reverse complement. Walks through the graph can therefore be used to represent longer sequences, found by concatenating the sequences of the nodes. We call walks used for this purpose paths , and they are usually stored along with the variation graph that they are inside of. Paths in a variation graph usually correspond to a small number of reference sequences. In addition to the reference sequences, Giraffe also uses a larger panel of haplotype paths, stored in a Graph Burrows-Wheeler Transform or GBWT index [ 49 ]. Originally, GBWT indexes were stored separately from their graphs, but the GBZ format [ 50 ] was developed to store them together, by storing the GBWT and a “GBWT graph” of node sequences in the same file, and storing non-haplotype paths along with the haplotypes in the GBWT. Because we found GBZ graphs so easy to work with, Giraffe now always uses the GBZ format. One subtlety is that a GBZ uses the paths in the GBWT to implicitly define the edges of the graph. Thus, a GBZ graph represents the subgraph of some original sequence graph whose edges are supported by the haplotypes and reference paths in the pangenome. Giraffe uses a distance index [ 51 ] to find minimum distances between positions in the graph. The distance index is based on decomposing the graph into snarls [ 52 ], which are sites of variation in the graph where paths can diverge to represent different alleles. Formally, a snarl is a subgraph defined by two boundary node sides that are separable and minimal . Two nodes sides are separable if cutting their nodes into their component node sides makes the subgraph between them unreachable from the rest of the graph. The two boundary node sides are minimal if no other node side within the subgraph is separable with either of the boundaries. Snarls often occur consecutively, with boundaries on opposite sides of shared nodes between them. A maximal length run of one or more nodes, with snarls between each node and the next, is called a chain . (These chains of snarls are not to be confused with the chains of alignment seeds used later.) The simplest possible chain is just a single node, so every node exists in some chain. More complex chains can be nested within snarls to represent nested variation, such as a series of SNPs that occur within an insertion. The decomposition of the graph into nested snarls and chains is described by a snarl tree ( Figure 1 B ). Although formally the decomposition is not unique, we usually work with one decomposition at a time. 5.2 Giraffe algorithm The long read Giraffe algorithm follows the common seed-chain-extend strategy [ 11 ] for mapping algorithms ( Figure 1 ). As in the original short read algorithm, long read Giraffe uses a minimizer index over the sequences of haplotypes in the GBWT to find seed alignments ( Figure 1 C ). For long reads, we use weighted minimizers that prioritize those with fewer occurrences in the graph, and add a filter to skip minimizers with too many occurrences (Section S1). The seeds are then chained together ( Figure 1 D-E , Section S3). A chain of seeds (not to be confused with the chains of snarls used previously) is an ordered set of seeds that are co-linear in the read and the reference. In a graph context, this means that each seed must be reachable in the graph from the previous seed. Giraffe tries to find optimal chains that maximize the coverage in the read and minimize the expected cost of the gap (the difference between the distance between the seeds in the read and the distance between seeds in the graph) that will be taken between consecutive seeds. We use a gap cost based on that of Minimap2 [ 10 ]. To efficiently calculate reachability and distance in a graph, we use a novel data structure called a zip code tree that represents distances among a set of seeds ( Figure 1 D ). The zip code tree approximates a placement of seeds in an unrolled, acyclic view of the reference graph, providing a partial ordering of seeds that can be used to find distances for chaining (Figure S1, Section S2). Using distances calculated with the zip code tree, we are able to find reasonable chains in regions of the graph with complex topologies such as duplications (Figure S2) and inversions (Figure S3). The zip code tree is computed using small data structures called zip codes , that store, for each seed, information about the position’s placement on the snarl tree and associated distances (Section S2.3). Because of the cache-efficiency of these lightweight data structures, it is fast to sort and calculate distances among seeds to construct the zip code tree. A zip code tree is constructed for all seeds in a single read. Chaining is done using two passes of a dynamic programming algorithm (Section S3.1). Finally, the chain ( Figure 1 E ) is extended into an alignment between the read and the graph. Base-level alignment is done between consecutive seeds in the chain and out from the first and last seeds ( Figure 1 F , Section S4). We use a fast wave-front algorithm [ 53 , 54 , 55 ] for aligning substrings of the read to the haplotype sequences in the graph, both for between-seed alignment and anchored tail alignment. If this algorithm fails to find an alignment or is predicted to use too much memory (or for any alignment problem over 233 bases), we align to the graph itself, using a banded global aligner for aligning between seeds and a Single Instruction Multiple Data (SIMD)-accelerated X-drop aligner (called Dozeu) for aligning tails. These algorithms limit the size of the dynamic programming band to constrain the amount of time and memory used. 2.3 Pangenome-guided assembly overview Using Giraffe’s ability to align long reads to pangenomes, we can do haplotyperesolved pangenome-guided assembly of long reads. Here we focus on local assembly. Our method assembles a specified region of interest (ROI) using a personalizedpangenome-guided assembly workflow, depicted in Figure 6.1. The workflow takes as input a variation graph and the sample’s long reads. For this study, we used the HPRC-clipped pangenome graph. First, the variation graph is personalized based on the input reads [ 18 ] by sampling 16 haplotypes (without using --diploid-sampling, which would further downsample to two). Input reads are then mapped to this personalized graph using long read Giraffe. For a target ROI, all reads mapping to the region, along with the subgraph and its snarl distance index, are extracted. These serve as input for the subsequent anchor generation step. Anchors are defined as potentially haplotype-informative k-mers, and enable partitioning of reads by haplotype. They are generated from unique paths within leaf snarls (snarls that contain no other nested snarls). Anchors of a given snarl share common boundary nodes but differ at internal sentinel node(s) that represent allelic variation. An anchor is considered to be supported by a read only if the corresponding read subsequence aligns as an exact match to the anchor path. To mitigate phasing errors caused by noisy long read alignments, we perform a filtering step to remove anchors in unreliable snarls that exhibit inconsistent phasing relative to neighboring snarls. Finally, the complete set of read-supported anchors from the reliable snarls is passed to the Shasta assembler, which performs bubble cleanup and detangling to generate a phased assembly of the ROI. 6.1 Funding This work was supported in part by the National Human Genome Research Institute (NHGRI) under award numbers U01HG013748, U41HG010972 and U24HG011853. This project has received funding from the European Union’s Horizon 2020 Research and Innovation Staff Exchange programme under the Marie Skłodowska-Curie grant agreement No. 872539. 6.2 Author contributions Project design: B.P. Giraffe algorithm design and implementation: X.C., A.M.N., J.M.E., J.S., S.H., B.P. Pangenome-guided assembly: S.Ne., F.A., S.Na., K.K. Graph production: G.H. Structural variant analysis: J.M., X.C., A.M.N. Short variant analysis: A.C., K.S., P.-C.C., A.M.N., X.C. vg code contributions: A.M.N., X.C., J.M.E., J.S., J.M., G.H., F.O. Sample collection from DSD-TRN biobank: E.D. 6.3 Competing interests A.C., K.S., and P.-C.C. are employees of Google and own Alphabet stock as part of the standard compensation package. The remaining authors declare no competing interests. 6.4 Data and materials availability An archived copy of the code, graphs, DeepVariant models, and simulated reads (excluding R10 reads) used in this paper are available on Zenodo [ 56 ]. All data on Zenodo is also available at https://cgl.gi.ucsc.edu/data/lr-giraffe/ , along with the R10 simulated reads and HG002 real read sets used for mapping evaluations. These real read sets used for mapping and calling valuations are available on Zenodo, at https://cgl.gi.ucsc.edu/data/lr-giraffe/ , and are publicly available at https://s3-us-west-2.amazonaws.com/human-pangenomics/index.html?prefix=T2T/HG002/assemblies/polishing/HG002/v1.0/mapping/hifi_revio_pbmay24/ (HiFi reads), s3://ont-open-data/giab_2025.01/ (R10 reads), gs://brain-genomics-public/research/sequencing/fastq/novaseq/wgs_pcr_free/40x/ (Illumina reads), and https://s3-us-west-2.amazonaws.com/human-pangenomics/index.html?prefix=T2T/scratch/HG002/sequencing/element/trio/HG002/ins500_600/ (Element reads). The read sets used for training DeepVariant are also publicly available; for details see Section S5.4.1. The HG002 R10 reads used for the pangenome-guided assembly pipeline are publicly available from GIAB here https://epi2me.nanoporetech.com/giab-2025.01/ . The CAH samples are available from the authors upon request (see Section S6.1). The HPRC-d46 graph and HPRC-Minigraph graphs used for mapping and calling evaluations are available on Zenodo [ 56 ], at https://cgl.gi.ucsc.edu/data/lr-giraffe/ , and at https://s3-us-west-2.amazonaws.com/human-pangenomics/index.html?prefix=pangenomes/scratch/2025_02_28_minigraph_cactus/ . The personalized haplotype sampled graphs are not publicly available, but they can be recreated using HG002 read sets and the base HPRC-clipped graph, which is available on Zenodo [ 56 ] and at https://cgl.gi.ucsc.edu/data/lr-giraffe/ . The Snakemake workflow used for read mapping, alignment analyses, and variant calling is available at https://github.com/vgteam/long-read-giraffe-experiments/tree/main . The regional PGA Snakemake workflow used for HG002 testing is available at https://github.com/shlokanegi/pga_workflow/tree/lrg2025-paper . The latest version of the vg toolkit is released at https://github.com/vgteam/vg . Copies of each of these GitHub repositories are available on Zenodo [ 56 ]. 6 Acknowledgments Funder Information Declared National Human Genome Research Institute, https://ror.org/00baak391 , U01HG013748 , U41HG010972 , U24HG011853 European Union , 872539 References [1]. ↵ Ting Wang , Lucinda Antonacci-Fulton , Kerstin Howe , Heather A. Lawson , Julian K. Lucas , Adam M. Phillippy , Alice B. Popejoy , Mobin Asri , Caryn Carson , Mark J. P. Chaisson , Xian Chang , Robert Cook-Deegan , Adam L. Felsenfeld , Robert S. Fulton , Erik P. Garrison , Nanibaa’ A. Garrison , Tina A. Graves-Lindsay , Hanlee Ji , Eimear E. Kenny , Barbara A. Koenig , Daofeng Li , Tobias Marschall , Joshua F. McMichael , Adam M. Novak , Deepak Purushotham , Valerie A. Schneider , Baergen I. Schultz , Michael W. Smith , Heidi J. Sofia , Tsachy Weissman , Paul Flicek , Heng Li , Karen H. Miga , Benedict Paten , Erich D. Jarvis , Ira M. Hall , Evan E. Eichler , David Haussler , and the Human Pangenome Reference Consortium . The Human Pangenome Project: a global resource to map genomic diversity . Nature , 604 ( 7906 ): 437 – 446 , April 2022 . ISSN 0028-0836 , 1476-4687. doi: 10.1038/s41586-022-04601-8 . URL https://www.nature.com/articles/s41586-022-04601-8 . OpenUrl CrossRef PubMed [2]. ↵ Karen H. Miga and Ting Wang . The Need for a Human Pangenome Reference Sequence . Annual Review of Genomics and Human Genetics , 22 ( 1 ): 81 – 102 , August 2021 . ISSN 1527-8204 , 1545-293X. doi: 10.1146/annurev-genom-120120-081921 . URL https://www.annualreviews.org/doi/10.1146/annurev-genom-120120-081921 . OpenUrl CrossRef [3]. ↵ Yang Gao , Xiaofei Yang , Hao Chen , Xinjiang Tan , Zhaoqing Yang , Lian Deng , Baonan Wang , Shuang Kong , Songyang Li , Yuhang Cui , Chang Lei , Yimin Wang , Yuwen Pan , Sen Ma , Hao Sun , Xiaohan Zhao , Yingbing Shi , Ziyi Yang , Dongdong Wu , Shaoyuan Wu , Xingming Zhao , Binyin Shi , Li Jin , Zhibin Hu , Yan Lu , Jiayou Chu , Kai Ye , and Shuhua Xu . A pangenome reference of 36 Chinese populations . Nature , 619 ( 7968 ): 112 – 121 , July 2023 . ISSN 1476-4687 . doi: 10.1038/s41586-023-06173-7 . URL https://www.nature.com/articles/s41586-023-06173-7 . OpenUrl CrossRef [4]. ↵ Connor Littlefield , Jose M. Lazaro-Guevara , Devorah Stucki , Michael Lansford , Melissa H. Pezzolesi , Emma J. Taylor , Etoni-Ma’asi C. Wolfgramm , Jacob Taloa , Kime Lao , C. Dave C. Dumaguit , Perry G. Ridge , Justina P. Tavana , William L. Holland , Kalani L. Raphael , and Marcus G. Pezzolesi . A Draft Pacific Ancestry Pangenome Reference , August 2024 . URL https://www.biorxiv.org/content/10.1101/2024.08.07.606392v2 . [5]. ↵ Nasna Nassir , Mohamed A. Almarri , Muhammad Kumail , Nesrin Mohamed , Bipin Balan , Shehzad Hanif , Maryam AlObathani , Bassam Jamalalail , Hanan Elsokary , Dasuki Kondaramage , Suhana Shiyas , Noor Kosaji , Dharana Satsangi , Madiha Hamdi Saif Abdelmotagali , Ahmad Abou Tayoun , Olfat Zuhair Salem Ahmed , Douaa Fathi Youssef , Hanan Al Suwaidi , Ammar Albanna , Stefan Du Plessis , Hamda Hassan Khansaheb , Alawi Alsheikh-Ali , and Mohammed Uddin . A draft Arab pangenome reference , July 2024 . URL https://www.biorxiv.org/content/10.1101/2024.07.09.602638v1 . [6]. ↵ Wen-Wei Liao , Mobin Asri , Jana Ebler , Daniel Doerr , Marina Haukness , Glenn Hickey , Shuangjia Lu , Julian K. Lucas , Jean Monlong , Haley J. Abel , Silvia Buonaiuto , Xian H. Chang , Haoyu Cheng , Justin Chu , Vincenza Colonna , Jordan M. Eizenga , Xiaowen Feng , Christian Fischer , Robert S. Fulton , Shilpa Garg , Cristian Groza , Andrea Guarracino , William T. Harvey , Simon Heumos , Kerstin Howe , Miten Jain , Tsung-Yu Lu , Charles Markello , Fergal J. Martin , Matthew W. Mitchell , Katherine M. Munson , Moses Njagi Mwaniki , Adam M. Novak , Hugh E. Olsen , Trevor Pesout , David Porubsky , Pjotr Prins , Jonas A. Sibbesen , Jouni Sirén , Chad Tomlinson , Flavia Villani , Mitchell R. Vollger , Lucinda L. Antonacci-Fulton , Gunjan Baid , Carl A. Baker , Anastasiya Belyaeva , Konstantinos Billis , Andrew Carroll , Pi-Chuan Chang , Sarah Cody , Daniel E. Cook , Robert M. Cook-Deegan , Omar E. Cornejo , Mark Diekhans , Peter Ebert , Susan Fairley , Olivier Fedrigo , Adam L. Felsenfeld , Giulio Formenti , Adam Frankish , Yan Gao , Nanibaa’ A. Garrison , Carlos Garcia Giron , Richard E. Green , Leanne Haggerty , Kendra Hoekzema , Thibaut Hourlier , Hanlee P. Ji , Eimear E. Kenny , Barbara A. Koenig , Alexey Kolesnikov , Jan O. Korbel , Jennifer Kordosky , Sergey Koren , HoJoon Lee , Alexandra P. Lewis , Hugo Magalhães , Santiago Marco-Sola , Pierre Marijon , Ann McCartney , Jennifer McDaniel , Jacquelyn Mountcastle , Maria Nattestad , Sergey Nurk , Nathan D. Olson , Alice B. Popejoy , Daniela Puiu , Mikko Rautiainen , Allison A. Regier , Arang Rhie , Samuel Sacco , Ashley D. Sanders , Valerie A. Schneider , Baergen I. Schultz , Kishwar Shafin , Michael W. Smith , Heidi J. Sofia , Ahmad N. Abou Tayoun , Françoise Thibaud-Nissen , Francesca Floriana Tricomi , Justin Wagner , Brian Walenz , Jonathan M. D. Wood , Aleksey V. Zimin , Guillaume Bourque , Mark J. P. Chaisson , Paul Flicek , Adam M. Phillippy , Justin M. Zook , Evan E. Eichler , David Haussler , Ting Wang , Erich D. Jarvis , Karen H. Miga , Erik Garrison , Tobias Marschall , Ira M. Hall , Heng Li , and Benedict Paten . A draft human pangenome reference . Nature , 617 ( 7960 ): 312 – 324 , May 2023 . ISSN 0028-0836 , 1476-4687. doi: 10.1038/s41586-023-05896-x . URL https://www.nature.com/articles/s41586-023-05896-x . OpenUrl CrossRef PubMed [7]. ↵ Erik Garrison , Jouni Sirén , Adam M. Novak , Glenn Hickey , Jordan M. Eizenga , Eric T. Dawson , William Jones , Shilpa Garg , Charles Markello , Michael F. Lin , Benedict Paten , and Richard Durbin . Variation graph toolkit improves read mapping by representing genetic variation in the reference . Nature Biotechnology , 36 ( 9 ): 875 – 879 , October 2018 . ISSN 1546-1696 . doi: 10.1038/nbt.4227 . URL https://www.nature.com/articles/nbt.4227 . OpenUrl CrossRef PubMed [8]. ↵ Ben Langmead and Steven L Salzberg . Fast gapped-read alignment with Bowtie 2 . Nature methods , 9 ( 4 ): 357 – 359 , March 2012 . ISSN 1548-7091 . doi: 10.1038/nmeth.1923 . URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC3322381/ . OpenUrl CrossRef PubMed Web of Science [9]. ↵ Heng Li . Aligning sequence reads, clone sequences and assembly contigs with BWA-MEM . arXiv , May 2013 . [10]. ↵ Heng Li . New strategies to improve minimap2 alignment accuracy . Bioinformatics , 37 ( 23 ): 4572 – 4574 , December 2021 . ISSN 1367-4803 , 1367-4811. doi: 10.1093/bioinformatics/btab705 . URL https://academic.oup.com/bioinformatics/article/37/23/4572/6384570 . OpenUrl CrossRef PubMed [11]. ↵ Kristoffer Sahlin , Thomas Baudeau , Bastien Cazaux , and Camille Marchet . A survey of mapping algorithms in the long-reads era . Genome Biology , 24 ( 1 ): 133 , 2023 . OpenUrl CrossRef PubMed [12]. ↵ Christopher Lee , Catherine Grasso , and Mark F. Sharlow . Multiple sequence alignment using partial order graphs . Bioinformatics , 18 ( 3 ): 452 – 464 , March 2002 . ISSN 1367-4811 , 1367-4803. doi: 10.1093/bioinformatics/18.3.452 . URL https://academic.oup.com/bioinformatics/article/18/3/452/236691 . OpenUrl CrossRef PubMed Web of Science [13]. ↵ Catherine Grasso and Christopher Lee . Combining partial order alignment and progressive multiple sequence alignment increases alignment speed and scalability to very large alignment problems . Bioinformatics , 20 ( 10 ): 1546 – 1556 , July 2004 . ISSN 1367-4811 , 1367-4803. doi: 10.1093/bioinformatics/bth126 . URL https://academic.oup.com/bioinformatics/article/20/10/1546/237238 . OpenUrl CrossRef PubMed Web of Science [14]. ↵ Ricardo Baeza-Yates and Gaston H. Gonnet . A new approach to text searching . Communications of the ACM , 35 ( 10 ): 74 – 82 , October 1992 . ISSN 0001-0782 , 1557-7317. doi: 10.1145/135239.135243 . URL https://dl.acm.org/doi/10.1145/135239.135243 . OpenUrl CrossRef [15]. ↵ Gene Myers . A fast bit-vector algorithm for approximate string matching based on dynamic programming . Journal of the ACM , 46 ( 3 ): 395 – 415 , May 1999 . ISSN 0004-5411 , 1557-735X. doi: 10.1145/316542.316550 . URL https://dl.acm.org/doi/10.1145/316542.316550 . OpenUrl CrossRef Web of Science [16]. ↵ Mikko Rautiainen , Veli Mäkinen , and Tobias Marschall . Bit-parallel sequence-to-graph alignment . Bioinformatics , 35 ( 19 ): 3599 – 3607 , October 2019 . ISSN 1367-4803 , 1367-4811. doi: 10.1093/bioinformatics/btz162 . URL https://academic.oup.com/bioinformatics/article/35/19/3599/5372677 . OpenUrl CrossRef [17]. ↵ Jouni Sirén , Jean Monlong , Xian Chang , Adam M. Novak , Jordan M. Eizenga , Charles Markello , Jonas A. Sibbesen , Glenn Hickey , Pi-Chuan Chang , Andrew Carroll , Namrata Gupta , Stacey Gabriel , Thomas W. Blackwell , Aakrosh Ratan , Kent D. Taylor , Stephen S. Rich , Jerome I. Rotter , David Haussler , Erik Garrison , and Benedict Paten . Pangenomics enables genotyping of known structural variants in 5202 diverse genomes . Science , 374 ( 6574 ): abg8871 , December 2021 . ISSN 0036-8075 , 1095-9203. doi: 10.1126/science.abg8871 . URL https://www.science.org/doi/10.1126/science.abg8871 . OpenUrl CrossRef PubMed [18]. ↵ Jouni Sirén , Parsa Eskandar , Matteo Tommaso Ungaro , Glenn Hickey , Jordan M. Eizenga , Adam M. Novak , Xian Chang , Pi-Chuan Chang , Mikhail Kolmogorov , Andrew Carroll , Jean Monlong , and Benedict Paten . Personalized pangenome references . Nature Methods , 21 ( 11 ): 2017 – 2023 , November 2024 . ISSN 1548-7091 , 1548-7105. doi: 10.1038/s41592-024-02407-2 . URL https://www.nature.com/articles/s41592-024-02407-2 . OpenUrl CrossRef [19]. ↵ Aaron M. Wenger , Paul Peluso , William J. Rowell , Pi-Chuan Chang , Richard J. Hall , Gregory T. Concepcion , Jana Ebler , Arkarachai Fungtammasan , Alexey Kolesnikov , Nathan D. Olson , Armin Töpfer , Michael Alonge , Medhat Mahmoud , Yufeng Qian , Chen-Shan Chin , Adam M. Phillippy , Michael C. Schatz , Gene Myers , Mark A. DePristo , Jue Ruan , Tobias Marschall , Fritz J. Sedlazeck , Justin M. Zook , Heng Li , Sergey Koren , Andrew Carroll , David R. Rank , and Michael W. Hunkapiller . Accurate circular consensus long-read sequencing improves variant detection and assembly of a human genome . Nature Biotechnology , 37 ( 10 ): 1155 – 1162 , October 2019 . ISSN 1087-0156 , 1546-1696. doi: 10.1038/s41587-019-0217-9 . URL https://www.nature.com/articles/s41587-019-0217-9 . OpenUrl CrossRef PubMed [20]. ↵ Peter E. Warburton and Robert P. Sebra . Long-Read DNA Sequencing: Recent Advances and Remaining Challenges . Annual Review of Genomics and Human Genetics , 24 ( 1 ): 109 – 132 , August 2023 . ISSN 1527-8204 , 1545-293X. doi: 10.1146/annurev-genom-101722-103045 . URL https://www.annualreviews.org/doi/10.1146/annurev-genom-101722-103045 . OpenUrl CrossRef PubMed [21]. ↵ Miten Jain , Sergey Koren , Karen H Miga , Josh Quick , Arthur C Rand , Thomas A Sasani , John R Tyson , Andrew D Beggs , Alexander T Dilthey , Ian T Fiddes , Sunir Malla , Hannah Marriott , Tom Nieto , Justin O’Grady , Hugh E Olsen , Brent S Pedersen , Arang Rhie , Hollian Richardson , Aaron R Quinlan , Terrance P Snutch , Louise Tee , Benedict Paten , Adam M Phillippy , Jared T Simpson , Nicholas J Loman , and Matthew Loose . Nanopore sequencing and assembly of a human genome with ultra-long reads . Nature Biotechnology , 36 ( 4 ): 338 – 345 , 2018 . ISSN 1087-0156 . doi: 10.1038/nbt.4060 . URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5889714/ . OpenUrl CrossRef PubMed [22]. ↵ Bernard Y. Kim , Hannah R. Gellert , Samuel H. Church , Anton Suvorov , Sean S. Anderson , Olga Barmina , Sofia G. Beskid , Aaron A. Comeault , K. Nicole Crown , Sarah E. Diamond , Steve Dorus , Takako Fujichika , James A. Hemker , Jan Hrcek , Maaria Kankare , Toru Katoh , Karl N. Magnacca , Ryan A. Martin , Teruyuki Matsunaga , Matthew J. Medeiros , Danny E. Miller , Scott Pitnick , Michele Schiffer , Sara Simoni , Tessa E. Steenwinkel , Zeeshan A. Syed , Aya Takahashi , Kevin H.-C. Wei , Tsuya Yokoyama , Michael B. Eisen , Artyom Kopp , Daniel Matute , Darren J. Obbard , Patrick M. O’Grady , Donald K. Price , Masanori J. Toda , Thomas Werner , and Dmitri A. Petrov . Single-fly genome assemblies fill major phylogenomic gaps across the Drosophilidae Tree of Life . PLOS Biology , 22 ( 7 ): e3002697 , July 2024 . ISSN 1545-7885 . doi: 10.1371/journal.pbio.3002697 . URL https://journals.plos.org/plosbiology/article?id=10.1371/journal.pbio.3002697 . OpenUrl CrossRef PubMed [23]. ↵ Nikhita Damaraju , Angela L Miller , and Danny E Miller . Long-Read DNA and RNA Sequencing to Streamline Clinical Genetic Testing and Reduce Barriers to Comprehensive Genetic Testing . The Journal of Applied Laboratory Medicine , 9 ( 1 ): 138 – 150 , January 2024 . ISSN 2475-7241 . doi: 10.1093/jalm/jfad107 . URL https://academic.oup.com/jalm/article/9/1/138/7502994 . OpenUrl CrossRef PubMed [24]. ↵ Mikhail Kolmogorov , Kimberley J. Billingsley , Mira Mastoras , Melissa Meredith , Jean Monlong , Ryan Lorig-Roach , Mobin Asri , Pilar Alvarez Jerez , Laksh Malik , Ramita Dewan , Xylena Reed , Rylee M. Genner , Kensuke Daida , Sairam Behera , Kishwar Shafin , Trevor Pesout , Jeshuwin Prabakaran , Paolo Carnevali , Jianzhi Yang , Arang Rhie , Sonja W. Scholz , Bryan J. Traynor , Karen H. Miga , Miten Jain , Winston Timp , Adam M. Phillippy , Mark Chaisson , Fritz J. Sedlazeck , Cornelis Blauwendraat , and Benedict Paten . Scalable Nanopore sequencing of human genomes provides a comprehensive view of haplotype-resolved variation and methylation . Nature Methods , 20 ( 10 ): 1483 – 1492 , October 2023 . ISSN 1548-7091 , 1548-7105. doi: 10.1038/s41592-023-01993-x . URL https://www.nature.com/articles/s41592-023-01993-x . OpenUrl CrossRef PubMed [25]. ↵ M. Mahmoud , Y. Huang , K. Garimella , P. A. Audano , W. Wan , N. Prasad , R. E. Handsaker , S. Hall , A. Pionzio , M. C. Schatz , M. E. Talkowski , E. E. Eichler , S. E. Levy , and F. J. Sedlazeck . Utility of long-read sequencing for All of Us . Nature Communications , 15 ( 1 ): 837 , January 2024 . ISSN 2041-1723 . doi: 10.1038/s41467-024-44804-3 . URL https://www.nature.com/articles/s41467-024-44804-3 . OpenUrl CrossRef [26]. ↵ Heng Li , Xiaowen Feng , and Chong Chu . The design and construction of reference pangenome graphs with minigraph . Genome Biology , 21 ( 1 ): 265 , October 2020 . ISSN 1474-760X . doi: 10.1186/s13059-020-02168-z . URL https://doi.org/10.1186/s13059-020-02168-z . OpenUrl CrossRef PubMed [27]. ↵ Jyotshna Rajput , Ghanshyam Chandra , and Chirag Jain . Co-linear chaining on pangenome graphs . Algorithms for Molecular Biology , 19 ( 1 ): 4 , January 2024 . ISSN 1748-7188 . doi: 10.1186/s13015-024-00250-w . URL https://doi.org/10.1186/s13015-024-00250-w . OpenUrl CrossRef PubMed [28]. ↵ Jun Ma , Manuel Cáceres , Leena Salmela , Veli Mäkinen , and Alexandru I. Tomescu . Chaining for accurate alignment of erroneous long reads to acyclic variation graphs . Bioinformatics , 39 ( 8 ), August 2023 . doi: 10.1093/bioinformatics/btad460 . URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC10423031/ . OpenUrl CrossRef [29]. ↵ Ghanshyam Chandra and Chirag Jain . Gap-Sensitive Colinear Chaining Algorithms for Acyclic Pangenome Graphs . Journal of Computational Biology , 30 ( 11 ): 1182 – 1197 , November 2023 . ISSN 1557-8666 . doi: 10.1089/cmb.2023.0186 . URL https://www.liebertpub.com/doi/10.1089/cmb.2023.0186 . OpenUrl CrossRef PubMed [30]. ↵ Veli Mäkinen , Alexandru I. Tomescu , Anna Kuosmanen , Topi Paavilainen , Travis Gagie , and Rayan Chikhi . Sparse Dynamic Programming on DAGs with Small Width . ACM Transactions on Algorithms , 15 ( 2 ): 1 – 21 , April 2019 . ISSN 1549-6325 , 1549-6333. doi: 10.1145/3301312 . URL https://dl.acm.org/doi/10.1145/3301312 . OpenUrl CrossRef [31]. ↵ Ghanshyam Chandra , Daniel Gibney , and Chirag Jain . Haplotype-aware sequence alignment to pangenome graphs . Genome Research , 34 ( 9 ): 1265 – 1275 , September 2024 . ISSN 1088-9051 , 1549-5469. doi: 10.1101/gr.279143.124 . URL http://genome.cshlp.org/content/34/9/1265 . OpenUrl Abstract / FREE Full Text [32]. ↵ Mikko Rautiainen and Tobias Marschall . GraphAligner: rapid and versatile sequence-to-graph alignment . Genome Biology , 21 ( 1 ): 253 , September 2020 . ISSN 1474-760X . doi: 10.1186/s13059-020-02157-2 . URL https://doi.org/10.1186/s13059-020-02157-2 . OpenUrl CrossRef PubMed [33]. ↵ Haoyu Cheng , Gregory T Concepcion , Xiaowen Feng , Haowen Zhang , and Heng Li . Haplotype-resolved de novo assembly using phased assembly graphs with hifiasm . Nature methods , 18 ( 2 ): 170 – 175 , 2021 . OpenUrl CrossRef PubMed [34]. ↵ Chirag Jain , Arang Rhie , Nancy F. Hansen , Sergey Koren , and Adam M. Phillippy . Long-read mapping to repetitive reference sequences using Winnowmap2 . Nature Methods , 19 ( 6 ): 705 – 710 , June 2022 . ISSN 1548-7105 . doi: 10.1038/s41592-022-01457-8 . URL https://www.nature.com/articles/s41592-022-01457-8 . OpenUrl CrossRef PubMed [35]. ↵ PacificBiosciences/pbmm2 , July 2025 . URL https://github.com/PacificBiosciences/pbmm2 . original-date: 2017-11-12T13:19:24Z. [36]. ↵ Ryan Poplin , Pi-Chuan Chang , David Alexander , Scott Schwartz , Thomas Colthurst , Alexander Ku , Dan Newburger , Jojo Dijamco , Nam Nguyen , Pegah T Afshar , Sam S Gross , Lizzie Dorfman , Cory Y McLean , and Mark A DePristo . A universal SNP and small-indel variant caller using deep neural networks . Nature Biotechnology , 36 ( 10 ): 983 – 987 , November 2018 . ISSN 1087-0156 , 1546-1696. doi: 10.1038/nbt.4235 . URL https://www.nature.com/articles/nbt.4235 . OpenUrl CrossRef PubMed [37]. ↵ Illumina/hap.py , November 2020 . URL https://github.com/Illumina/hap.py . https://github.com/Illumina/hap.py . [38]. ↵ Peter Krusche , Len Trigg , Paul C. Boutros , Christopher E. Mason , Francisco M. De La Vega , Benjamin L. Moore , Mar Gonzalez-Porta , Michael A. Eberle , Zivana Tezak , Samir Lababidi , Rebecca Truty , George Asimenos , Birgit Funke , Mark Fleharty , Brad A. Chapman , Marc Salit , and Justin M. Zook . Best practices for benchmarking germline small-variant calls in human genomes . Nature Biotechnology , 37 ( 5 ): 555 – 560 , May 2019 . ISSN 1546-1696 . doi: 10.1038/s41587-019-0054-x . URL https://www.nature.com/articles/s41587-019-0054-x . OpenUrl CrossRef PubMed [39]. ↵ Justin Wagner , Nathan D. Olson , Lindsay Harris , Ziad Khan , Jesse Farek , Medhat Mahmoud , Ana Stankovic , Vladimir Kovacevic , Byunggil Yoo , Neil Miller , Jeffrey A. Rosenfeld , Bohan Ni , Samantha Zarate , Melanie Kirsche , Sergey Aganezov , Michael C. Schatz , Giuseppe Narzisi , Marta Byrska-Bishop , Wayne Clarke , Uday S. Evani , Charles Markello , Kishwar Shafin , Xin Zhou , Arend Sidow , Vikas Bansal , Peter Ebert , Tobias Marschall , Peter Lansdorp , Vincent Hanlon , Carl-Adam Mattsson , Alvaro Martinez Barrio , Ian T. Fiddes , Chunlin Xiao , Arkarachai Fungtammasan , Chen-Shan Chin , Aaron M. Wenger , William J. Rowell , Fritz J. Sedlazeck , Andrew Carroll , Marc Salit , and Justin M. Zook . Benchmarking challenging small variants with linked and long reads . Cell Genomics , 2 ( 5 ): 100128 , May 2022 . ISSN 2666979X . doi: 10.1016/j.xgen.2022.100128 . URL https://linkinghub.elsevier.com/retrieve/pii/S2666979X2200057X . OpenUrl CrossRef PubMed [40]. ↵ Mobin Asri , Pi-Chuan Chang , Juan Carlos Mier , Jouni Sirén , Parsa Eskandar , Alexey Kolesnikov , Daniel E. Cook , Lucas Brambrink , Glenn Hickey , Adam M. Novak , Lizzie Dorfman , Dale R. Webster , Andrew Carroll , Benedict Paten , and Kishwar Shafin . Pangenome-aware DeepVariant , June 2025 . URL http://biorxiv.org/lookup/doi/10.1101/2025.06.05.657102 . [41]. ↵ Glenn Hickey , David Heller , Jean Monlong , Jonas A. Sibbesen , Jouni Sirén , Jordan Eizenga , Eric T. Dawson , Erik Garrison , Adam M. Novak , and Benedict Paten . Genotyping structural variants in pangenome graphs using the vg toolkit . Genome Biology , 21 ( 1 ): 35 , February 2020 . ISSN 1474-760X . doi: 10.1186/s13059-020-1941-7 . URL https://doi.org/10.1186/s13059-020-1941-7 . OpenUrl CrossRef PubMed [42]. ↵ Fritz J. Sedlazeck , Philipp Rescheneder , Moritz Smolka , Han Fang , Maria Nattestad , Arndt von Haeseler , and Michael C. Schatz . Accurate detection of complex structural variations using single-molecule sequencing . Nature Methods , 15 ( 6 ): 461 – 468 , June 2018 . ISSN 1548-7105 . doi: 10.1038/s41592-018-0001-7 . URL https://www.nature.com/articles/s41592-018-0001-7 . OpenUrl CrossRef PubMed [43]. ↵ Moritz Smolka , Luis F. Paulin , Christopher M. Grochowski , Dominic W. Horner , Medhat Mahmoud , Sairam Behera , Ester Kalef-Ezra , Mira Gandhi , Karl Hong , Davut Pehlivan , Sonja W. Scholz , Claudia M. B. Carvalho , Christos Proukakis , and Fritz J. Sedlazeck . Detection of mosaic and population-level structural variants with Sniffles2 . Nature Biotechnology , 42 ( 10 ): 1571 – 1580 , October 2024 . ISSN 1546-1696 . doi: 10.1038/s41587-023-02024-y . URL https://www.nature.com/articles/s41587-023-02024-y . OpenUrl CrossRef [44]. ↵ Justin M. Zook , Nancy F. Hansen , Nathan D. Olson , Lesley M. Chapman , James C. Mullikin , Chunlin Xiao , Stephen Sherry , Sergey Koren , Adam M. Phillippy , Paul C. Boutros , Sayed Mohammad E. Sahraeian , Vincent Huang , Alexandre Rouette , Noah Alexander , Christopher E. Mason , Iman Hajirasouliha , Camir Ricketts , Joyce Lee , Rick Tearle , Ian T. Fiddes , Alvaro Martinez Barrio , Jeremiah Wala , Andrew Carroll , Noushin Ghaffari , Oscar L. Rodriguez , Ali Bashir , Shaun Jackman , John J Farrell , Aaron M Wenger , Can Alkan , Arda Soylev , Michael C. Schatz , Shilpa Garg , George Church , Tobias Marschall , Ken Chen , Xian Fan , Adam C. English , Jeffrey A. Rosenfeld , Weichen Zhou , Ryan E. Mills , Jay M. Sage , Jennifer R. Davis , Michael D. Kaiser , John S. Oliver , Anthony P. Catalano , Mark JP Chaisson , Noah Spies , Fritz J. Sedlazeck , and Marc Salit . A robust benchmark for detection of germline large deletions and insertions . Nature biotechnology , 38 ( 11 ): 1347 – 1355 , November 2020 . ISSN 1087-0156 . doi: 10.1038/s41587-020-0538-8 . URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC8454654/ . OpenUrl CrossRef PubMed [45]. ↵ Adam C. English , Vipin K. Menon , Richard A. Gibbs , Ginger A. Metcalf , and Fritz J. Sedlazeck . Truvari: refined structural variant comparison preserves allelic diversity . Genome Biology , 23 ( 1 ): 271 , December 2022 . ISSN 1474-760X . doi: 10.1186/s13059-022-02840-6 . URL https://doi.org/10.1186/s13059-022-02840-6 . OpenUrl CrossRef PubMed [46]. ↵ Shloka Negi , Sarah L. Stenton , Seth I. Berger , Paolo Canigiula , Brandy McNulty , Ivo Violich , Joshua Gardner , Todd Hillaker , Sara M. O’Rourke , Melanie C. O’Leary , Elizabeth Carbonell , Christina Austin-Tse , Gabrielle Lemire , Jillian Serrano , Brian Mangilog , Grace VanNoy , Mikhail Kolmogorov , Eric Vilain , Anne O’Donnell-Luria , Emmanuele Délot , Karen H. Miga , Jean Monlong , and Benedict Paten . Advancing long-read nanopore genome assembly and accurate variant calling for rare disease detection . The American Journal of Human Genetics , 112 ( 2 ): 428 – 449 , 2025 . ISSN 0002-9297 . doi: 10.1016/j.ajhg.2025.01.002 . URL https://www.sciencedirect.com/science/article/pii/S0002929725000023 . OpenUrl CrossRef [47]. ↵ Jean Monlong , Xiao Chen , Hayk Barseghyan , William J Rowell , Shloka Negi , Natalie Nokoff , Lauren Mohnach , Josephine Hirsch , Courtney Finlayson , Catherine E. Keegan , Miguel Almalvez , Seth I. Berger , Ivan de Dios , Brandy McNulty , Alex Robertson , Karen H. Miga , Phyllis W. Speiser , Benedict Paten , Eric Vilain , and Emmanuele C. Délot . Long-read sequencing resolves the clinically relevant cyp21a2 locus, supporting a new clinical test for congenital adrenal hyperplasia . medRxiv , 2025 . doi: 10.1101/2025.02.07.25321404 . URL https://www.medrxiv.org/content/early/2025/02/10/2025.02.07.25321404 . OpenUrl Abstract / FREE Full Text [48]. ↵ Erik Garrison , Andrea Guarracino , Simon Heumos , Flavia Villani , Zhigui Bao , Lorenzo Tattini , Jörg Hagmann , Sebastian Vorbrugg , Santiago Marco-Sola , Christian Kubica , David G. Ashbrook , Kaisa Thorell , Rachel L. Rusholme-Pilcher , Gianni Liti , Emilio Rudbeck , Agnieszka A. Golicz , Sven Nahnsen , Zuyu Yang , Moses Njagi Mwaniki , Franklin L. Nobrega , Yi Wu , Hao Chen , Joep De Ligt , Peter H. Sudmant , Sanwen Huang , Detlef Weigel , Nicole Soranzo , Vincenza Colonna , Robert W. Williams , and Pjotr Prins . Building pangenome graphs . Nature Methods , 21 ( 11 ): 2008 – 2012 , November 2024 . ISSN 1548-7091 , 1548-7105. doi: 10.1038/s41592-024-02430-3 . URL https://www.nature.com/articles/s41592-024-02430-3 . OpenUrl CrossRef [49]. ↵ Jouni Sirén , Erik Garrison , Adam M Novak , Benedict Paten , and Richard Durbin . Haplotype-aware graph indexes . Bioinformatics , 36 ( 2 ): 400 – 407 , January 2020 . ISSN 1367-4803 , 1367-4811. doi: 10.1093/bioinformatics/btz575 . URL https://academic.oup.com/bioinformatics/article/36/2/400/5538990 . OpenUrl CrossRef PubMed [50]. ↵ Jouni Sirén and Benedict Paten . BZ file format for pangenome graphs . Bioinformatics , 38 ( 22 ): 5012 – 5018 , November 2022 . ISSN 1367-4803 , 1367-4811. doi: 10.1093/bioinformatics/btac656 . URL https://academic.oup.com/bioinformatics/article/38/22/5012/6731924 . OpenUrl CrossRef [51]. ↵ Xian Chang , Jordan Eizenga , Adam M Novak , Jouni Sirén , and Benedict Paten . Distance indexing and seed clustering in sequence graphs . Bioinformatics , 36 (Supplement 1 ): i146 – i153 , July 2020 . ISSN 1367-4803 , 1367-4811. doi: 10.1093/bioinformatics/btaa446 . URL https://academic.oup.com/bioinformatics/article/36/Supplement_1/i146/5870464 . OpenUrl CrossRef PubMed [52]. ↵ Benedict Paten , Jordan M. Eizenga , Yohei M. Rosen , Adam M. Novak , Erik Garrison , and Glenn Hickey . Superbubbles, Ultrabubbles, and Cacti . Journal of Computational Biology , 25 ( 7 ): 649 – 663 , July 2018 . ISSN 1557-8666 . doi: 10.1089/cmb.2017.0251 . URL http://www.liebertpub.com/doi/10.1089/cmb.2017.0251 . OpenUrl CrossRef PubMed [53]. ↵ Santiago Marco-Sola , Juan Carlos Moure , Miquel Moreto , and Antonio Espinosa . Fast gap-affine pairwise alignment using the wavefront algorithm . Bioinformatics , 37 ( 4 ): 456 – 463 , May 2021 . ISSN 1367-4803 , 1367-4811. doi: 10.1093/bioinformatics/btaa777 . URL https://academic.oup.com/bioinformatics/article/37/4/456/5904262 . OpenUrl CrossRef PubMed [54]. ↵ Jordan M. Eizenga and Benedict Paten . Improving the time and space complexity of the WFA algorithm and generalizing its scoring , January 2022 . URL http://biorxiv.org/lookup/doi/10.1101/2022.01.12.476087 . [55]. ↵ Santiago Marco-Sola , Jordan M Eizenga , Andrea Guarracino , Benedict Paten , Erik Garrison , and Miquel Moreto . Optimal gapaffine alignment in O (s) space . Bioinformatics , 39 ( 2 ): btad074 , February 2023 . ISSN 1367-4811 . doi: 10.1093/bioinformatics/btad074 . URL https://academic.oup.com/bioinformatics/article/doi/10.1093/bioinformatics/btad074/7030690 . OpenUrl CrossRef PubMed [56]. ↵ Xian Chang , Adam Novak , Jordan Eizenga , Jouni Sirén , Jean Monlong , Shloka Negi , Francesco Andreace , Sagorika Nag , Konstantinos Kyriakidis , Glenn Hickey , Stephen Hwang , Emmanuele Délot , Andrew Carroll , Kishwar Shafin , Pi-Chuan Chang , Faith Okamoto , and Benedict Paten . Software and products for “Rapid, accurate long- and short-read mapping to large pangenome graphs with vg Giraffe” , September 2025 . URL https://zenodo.org/doi/10.5281/zenodo.17169602 . [57]. Chirag Jain , Arang Rhie , Haowen Zhang , Claudia Chu , Brian P Walenz , Sergey Koren , and Adam M Phillippy . Weighted minimizer sampling improves long read mapping . Bioinformatics , 36 (Supplement 1 ): i111 – i118 , July 2020 . ISSN 1367-4803 , 1367-4811. doi: 10.1093/bioinformatics/btaa435 . URL https://academic.oup.com/bioinformatics/article/36/Supplement_1/i111/5870473 . OpenUrl CrossRef PubMed [58]. Ittai Abraham , Daniel Delling , Andrew V Goldberg , and Renato F Werneck . Hierarchical hub labelings for shortest paths . In European Symposium on Algorithms , pages 24 – 35 . Springer , 2012 . [59]. Sergey Nurk , Sergey Koren , Arang Rhie , Mikko Rautiainen , Andrey V. Bzikadze , Alla Mikheenko , Mitchell R. Vollger , Nicolas Altemose , Lev Uralsky , Ariel Gershman , Sergey Aganezov , Savannah J. Hoyt , Mark Diekhans , Glennis A. Logsdon , Michael Alonge , Stylianos E. Antonarakis , Matthew Borchers , Gerard G. Bouffard , Shelise Y. Brooks , Gina V. Caldas , Nae-Chyun Chen , Haoyu Cheng , Chen-Shan Chin , William Chow , Leonardo G. De Lima , Philip C. Dishuck , Richard Durbin , Tatiana Dvorkina , Ian T. Fiddes , Giulio Formenti , Robert S. Fulton , Arkarachai Fungtammasan , Erik Garrison , Patrick G. S. Grady , Tina A. Graves-Lindsay , Ira M. Hall , Nancy F. Hansen , Gabrielle A. Hartley , Marina Haukness , Kerstin Howe , Michael W. Hunkapiller , Chirag Jain , Miten Jain , Erich D. Jarvis , Peter Kerpedjiev , Melanie Kirsche , Mikhail Kolmogorov , Jonas Korlach , Milinn Kremitzki , Heng Li , Valerie V. Maduro , Tobias Marschall , Ann M. McCartney , Jennifer McDaniel , Danny E. Miller , James C. Mullikin , Eugene W. Myers , Nathan D. Olson , Benedict Paten , Paul Peluso , Pavel A. Pevzner , David Porubsky , Tamara Potapova , Evgeny I. Rogaev , Jeffrey A. Rosenfeld , Steven L. Salzberg , Valerie A. Schneider , Fritz J. Sedlazeck , Kishwar Shafin , Colin J. Shew , Alaina Shumate , Ying Sims , Arian F. A. Smit , Daniela C. Soto , Ivan Sović , Jessica M. Storer , Aaron Streets , Beth A. Sullivan , Françoise Thibaud-Nissen , James Torrance , Justin Wagner , Brian P. Walenz , Aaron Wenger , Jonathan M. D. Wood , Chunlin Xiao , Stephanie M. Yan , Alice C. Young , Samantha Zarate , Urvashi Surti , Rajiv C. McCoy , Megan Y. Dennis , Ivan A. Alexandrov , Jennifer L. Gerton , Rachel J. O’Neill , Winston Timp , Justin M. Zook , Michael C. Schatz , Evan E. Eichler , Karen H. Miga , and Adam M. Phillippy . The complete sequence of a human genome . Science , 376 ( 6588 ): 44 – 53 , April 2022 . ISSN 0036-8075 , 1095-9203. doi: 10.1126/science.abj6987 . URL https://www.science.org/doi/10.1126/science.abj6987 . OpenUrl CrossRef PubMed [60]. Justin M. Zook , David Catoe , Jennifer McDaniel , Lindsay Vang , Noah Spies , Arend Sidow , Ziming Weng , Yuling Liu , Christopher E. Mason , Noah Alexander , Elizabeth Henaff , Alexa B. R. McIntyre , Dhruva Chandramohan , Feng Chen , Erich Jaeger , Ali Moshrefi , Khoa Pham , William Stedman , Tiffany Liang , Michael Saghbini , Zeljko Dzakula , Alex Hastie , Han Cao , Gintaras Deikus , Eric Schadt , Robert Sebra , Ali Bashir , Rebecca M. Truty , Christopher C. Chang , Natali Gulbahce , Keyan Zhao , Srinka Ghosh , Fiona Hyland , Yutao Fu , Mark Chaisson , Chunlin Xiao , Jonathan Trow , Stephen T. Sherry , Alexander W. Zaranek , Madeleine Ball , Jason Bobe , Preston Estep , George M. Church , Patrick Marks , Sofia Kyriazopoulou-Panagiotopoulou , Grace X. Y. Zheng , Michael Schnall-Levin , Heather S. Ordonez , Patrice A. Mudivarti , Kristina Giorda , Ying Sheng , Karoline Bjarnesdatter Rypdal , and Marc Salit . Extensive sequencing of seven human genomes to characterize benchmark reference materials . Scientific Data , 3 ( 1 ): 160025 , June 2016 . ISSN 2052-4463 . doi: 10.1038/sdata.2016.25 . URL https://www.nature.com/articles/sdata201625 . OpenUrl CrossRef PubMed [61]. Gunjan Baid , Maria Nattestad , Alexey Kolesnikov , Sidharth Goel , Howard Yang , Pi-Chuan Chang , and Andrew Carroll . An extensive sequence dataset of gold-standard samples for benchmarking and development . bioRxiv , 2020 . doi: 10.1101/2020.12.11.422022 . URL https://www.biorxiv.org/content/early/2020/12/11/2020.12.11.422022 . OpenUrl Abstract / FREE Full Text [62]. Yukiteru Ono , Kiyoshi Asai , and Michiaki Hamada . Pbsim2: a simulator for long-read sequencers with a novel generative model of quality scores . Bioinformatics , 37 ( 5 ): 589 – 595 , 09 2020 . ISSN 1367-4803 . doi: 10.1093/bioinformatics/btaa835 . URL https://doi.org/10.1093/bioinformatics/btaa835 . OpenUrl CrossRef [63]. Silvia Liu , Caroline Obert , Yan-Ping Yu , Junhua Zhao , Bao-Guo Ren , Jia-Jun Liu , Kelly Wiseman , Benjamin J. Krajacich , Wenjia Wang , Kyle Metcalfe , Mat Smith , Tuval Ben-Yehezkel , and Jian-Hua Luo . Utility analyses of AVITI sequencing chemistry . BMC Genomics , 25 : 778 , August 2024 . ISSN 1471-2164 . doi: 10.1186/s12864-024-10686-4 . URL https://www.ncbi.nlm.nih.gov/pmc/articles/PMC11316309/ . OpenUrl CrossRef PubMed [64]. Nathan D Olson , Justin Wagner , Jennifer McDaniel , Sarah H Stephens , Samuel T Westreich , Anish G Prasanna , Elaine Johanson , Emily Boja , Ezekiel J Maier , Omar Serang , et al. Precisionfda truth challenge v2: Calling variants from short and long reads in difficult-to-map regions . Cell genomics , 2 ( 5 ), 2022 . [65]. github.com/vgteam/vg wdl/DeepVariant , July 2025 . URL https://zenodo.org/doi/10.5281/zenodo.17081107 . [66]. John Vivian , Arjun Arkal Rao , Frank Austin Nothaft , Christopher Ketchum , Joel Armstrong , Adam Novak , Jacob Pfeil , Jake Narkizian , Alden D Deran , Audrey Musselman-Brown , et al. Toil enables reproducible, open source, big biomedical data analyses . Nature biotechnology , 35 ( 4 ): 314 – 316 , 2017 . OpenUrl CrossRef PubMed [67]. Erik Garrison , Zev N. Kronenberg , Eric T. Dawson , Brent S. Pedersen , and Pjotr Prins . A spectrum of free software tools for processing the VCF variant call format: vcflib, bio-vcf, cyvcf2, hts-nim and slivar . PLOS Computational Biology , 18 ( 5 ): e1009123 , May 2022 . ISSN 1553-7358 . doi: 10.1371/journal.pcbi.1009123 . URL https://dx.plos.org/10.1371/journal.pcbi.1009123 . OpenUrl CrossRef PubMed [68]. Cinzia Carrozza , Laura Foca , Elisa De Paolis , and Paola Concolino . Genes and pseudogenes: complexity of the rccx locus and disease . Frontiers in Endocrinology , 12 : 709758 , 2021 . OpenUrl PubMed [69]. Vladimir V Shiryagin , Andrey A Devyatkin , Oleg D Fateev , Ekaterina S Petriaikina , Viktor P Bogdanov , Zoia G Antysheva , Pavel Yu Volchkov , Sergey M Yudin , Mary Woroncow , and Veronika I Skvortsova . Genomic complexity and clinical significance of the rccx locus . PeerJ , 12 : e18243 , 2024 . OpenUrl PubMed [70]. Hedi L Claahsen-Van Der Grinten , Phyllis W Speiser , S Faisal Ahmed , Wiebke Arlt , Richard J Auchus , Henrik Falhammar , Christa E Flück , Leonardo Guasti , Angela Huebner , Barbara BM Kortmann , et al. Congenital adrenal hyperplasia—current insights in pathophysiology, diagnostics, and management . Endocrine reviews , 43 ( 1 ): 91 – 159 , 2022 . OpenUrl PubMed [71]. Grant H Burch , Yan Gong , Wenhui Liu , Robert W Dettman , Cynthia J Curry , Lynne Smith , Walter L Miller , and James Bristow . Tenascin–x deficiency is associated with ehlers–danlos syndrome . Nature genetics , 17 ( 1 ): 104 – 108 , 1997 . OpenUrl CrossRef PubMed Web of Science [72]. Joost Schalkwijk , Manon C Zweers , Peter M Steijlen , Willow B Dean , Glen Taylor , Ivonne M van Vlijmen , Brigitte van Haren , Walter L Miller , and James Bristow . A recessive form of the ehlers–danlos syndrome caused by tenascin-x deficiency . New England Journal of Medicine , 345 ( 16 ): 1167 – 1175 , 2001 . OpenUrl CrossRef PubMed Web of Science [73]. Nolan Kamitaki , Aswin Sekar , Robert E Handsaker , Heather De Rivera , Katherine Tooley , David L Morris , Kimberly E Taylor , Christopher W Whelan , Philip Tombleson , Loes M Olde Loohuis , et al. Complement genes contribute sex-biased vulnerability in diverse disorders . Nature , 582 ( 7813 ): 577 – 581 , 2020 . OpenUrl CrossRef PubMed [74]. Walter L Miller . Tenascin-x—discovery and early research . Frontiers in Immunology , 11 : 612497 , 2021 . OpenUrl PubMed View the discussion thread. Back to top Previous Next Posted October 01, 2025. Download PDF Supplementary Material Email Thank you for your interest in spreading the word about bioRxiv. NOTE: Your email address is requested solely to identify you as the sender of this article. Your Email * Your Name * Send To * Enter multiple addresses on separate lines or separate them with commas. You are going to email the following Rapid, accurate long- and short-read mapping to large pangenome graphs with vg Giraffe Message Subject (Your Name) has forwarded a page to you from bioRxiv Message Body (Your Name) thought you would like to see this page from the bioRxiv website. Your Personal Message CAPTCHA This question is for testing whether or not you are a human visitor and to prevent automated spam submissions. Share Rapid, accurate long- and short-read mapping to large pangenome graphs with vg Giraffe Xian Chang , Adam M. Novak , Jordan M. Eizenga , Jouni Sirén , Jean Monlong , Shloka Negi , Francesco Andreace , Sagorika Nag , Konstantinos Kyriakidis , Glenn Hickey , Stephen Hwang , Emmanuèle C. Délot , Andrew Carroll , Kishwar Shafin , Pi-Chuan Chang , Faith Okamoto , Benedict Paten , the Human Pangenome Reference Consortium bioRxiv 2025.09.29.678807; doi: https://doi.org/10.1101/2025.09.29.678807 Share This Article: Copy Citation Tools Rapid, accurate long- and short-read mapping to large pangenome graphs with vg Giraffe Xian Chang , Adam M. Novak , Jordan M. Eizenga , Jouni Sirén , Jean Monlong , Shloka Negi , Francesco Andreace , Sagorika Nag , Konstantinos Kyriakidis , Glenn Hickey , Stephen Hwang , Emmanuèle C. Délot , Andrew Carroll , Kishwar Shafin , Pi-Chuan Chang , Faith Okamoto , Benedict Paten , the Human Pangenome Reference Consortium bioRxiv 2025.09.29.678807; doi: https://doi.org/10.1101/2025.09.29.678807 Citation Manager Formats BibTeX Bookends EasyBib EndNote (tagged) EndNote 8 (xml) Medlars Mendeley Papers RefWorks Tagged Ref Manager RIS Zotero Tweet Widget Facebook Like Google Plus One Subject Area Bioinformatics Subject Areas All Articles Animal Behavior and Cognition (7617) Biochemistry (17633) Bioengineering (13856) Bioinformatics (41841) Biophysics (21399) Cancer Biology (18529) Cell Biology (25422) Clinical Trials (138) Developmental Biology (13352) Ecology (19860) Epidemiology (2067) Evolutionary Biology (24281) Genetics (15582) Genomics (22461) Immunology (17700) Microbiology (40293) Molecular Biology (17140) Neuroscience (88413) Paleontology (666) Pathology (2823) Pharmacology and Toxicology (4813) Physiology (7632) Plant Biology (15107) Scientific Communication and Education (2042) Synthetic Biology (4284) Systems Biology (9808) Zoology (2267)