Source-linked AI summary
Scalable telomere-to-telomere assembly for diploid and polyploid genomes with double graph
Haoyu Cheng, Mobin Asri, Julian Lucas, Sergey Koren, Heng Li
TL;DR
Ultra-long-read overlaps are costly to compute and difficult to identify accurately, while HiFi graphs can retain unresolved tangles. Hifiasm (UL) builds and merges HiFi and ultra-long-read graphs, then uses graph binning for haplotype-resolved assembly. Its integer contigs can be longer than individual ultra-long reads, and its polyploid workflow discards nodes marked for other haplotypes when emitting an assembly.
Problem
Constructing an ultra-long-read string graph requires costly all-versus-all comparisons, and high error rates make correct overlaps difficult to identify, especially in difficult regions.
Source: Methods · p. 6Method
Hifiasm (UL) builds separate HiFi and ultra-long-read graphs, maps ultra-long reads into integer sequences, and merges the resulting contigs into the HiFi graph for haplotype binning.
Source: Methods · pp. 4, 6, 7Results
Integer contigs are significantly longer than individual ultra-long reads and represent paths that can untangle intricate structures in the initial HiFi graph.
Source: Methods · p. 6Takeaways & Limitations
For polyploid genomes, the graph-binning approach discards nodes marked for other haplotypes when emitting each haplotype's assembly.
Source: Methods · p. 7HPRC Year 2 assemblies used ultra-long reads of at least 100 kb, while Year 1 assemblies used a 50 kb minimum because too few Year 1 reads were at least 100 kb.
Source: §1.8 · p. 14
Abstract
from arXiv · showhide
Despite recent advances in the length and the accuracy of long-read data, building haplotype-resolved genome assemblies from telomere to telomere still requires considerable computational resources. In this study, we present an efficient de novo assembly algorithm that combines multiple sequencing technologies to scale up population-wide telomere-to-telomere assemblies. By utilizing twenty-two human and two plant genomes, we demonstrate that our algorithm is around an order of magnitude cheaper than existing methods, while producing better diploid and haploid assemblies. Notably, our algorithm is the only feasible solution to the haplotype-resolved assembly of polyploid genomes.
Methods
Hifiasm (UL) builds separate HiFi and ultra-long-read graphs, then merges them to form an assembly graph for haplotype resolution. Its integer-graph workflow uses ultra-long-read alignments to preserve useful HiFi graph structure and resolve tangled paths.
Methods
- Hifiasm (UL) builds separate HiFi and ultra-long-read string graphs and merges them into a final assembly graph, using HiFi as the accurate backbone.This double-graph approach also incorporates information among ultra-long reads that accurate-read-first methods disregard.Source: Methods · pp. 4–5
- Ultra-long-read alignments identify critical contained HiFi reads and count read support for graph edges, informing graph construction and cleaning.The method retains contained reads that must be covered by ultra-long-read alignments and can remove those that can be skipped.Source: Methods · pp. 5–6, Figure 1 · p. 5
- Ultra-long reads are mapped to sequences of HiFi graph node identifiers, and exact overlaps among these integer sequences form a lightweight integer graph.Graph alignment corrects ultra-long-read errors before overlap detection, avoiding all-versus-all base-level read comparison.Source: Methods · p. 6
- The integer graph is aggressively cleaned to remove ambiguous edges, taking advantage of ultra-long reads that can span repetitive or homozygous regions.Each graph node represents an ultra-long integer sequence, and edges represent exact overlaps.Source: Methods · p. 6
- Integer contigs are non-branching graph paths concatenated into sequences longer than individual ultra-long reads, helping untangle structures in the HiFi graph.These contigs represent assembly paths in the initial HiFi graph.Source: Methods · p. 6
- The final graph is formed by replacing shared HiFi nodes with ultra-long integer contigs, then graph binning produces haplotype-resolved assemblies from Hi-C or parental markers.For polyploid genomes, nodes marked for other haplotypes are discarded when emitting each haplotype's assembly.Source: Methods · p. 7
Reporting Summary
The section points readers to an external research-design reporting summary.
Reporting Summary
- Further research-design information is available in the linked Nature Research Reporting Summary.Source: Reporting Summary · p. 8
1 Software commands
The software-command section gives read-filtering thresholds for different datasets.
1.1 Filtering ultra-long reads
- Ultra-long reads shorter than 100 kb were removed for HPRC Year 2, while reads shorter than 50 kb were removed for HPRC Year 1 and plant samples.The section includes seqkit commands for filtering these reads.Source: §1.1 · p. 9
1.2 Hifiasm
The commands configure hifiasm for Hi-C, trio-binning, haploid Arabidopsis, and potato assemblies, with separate potato commands with and without ultra-long reads.
1.2 Hifiasm
- Hi-C phased assemblies use HiFi, Hi-C, and ultra-long reads, with Hi-C read pairs supplied through the --h1 and --h2 options.Source: §1.2 · p. 9
- Trio-binning builds paternal and maternal yak indexes from parental short reads, then supplies those indexes and HiFi and ultra-long reads to hifiasm.Source: §1.2 · p. 9
- Haploid Arabidopsis assemblies are run with HiFi and ultra-long reads, while a separate command produces a HiFi-only assembly.Source: §1.2 · p. 9
- The potato commands use HiFi reads and a genetic map, with one command adding ultra-long reads and another omitting them.Source: §1.2 · p. 9
1.3 Verkko
Verkko was run with HiFi and ultra-long reads for haploid Arabidopsis assembly and with parental hapmer databases for trio-binning. For human Hi-C assemblies, an unphased Verkko graph was phased with gfase, then Verkko was rerun with the phasing results.
1.3 Verkko
- Haploid Arabidopsis assembly used Verkko 1.3.1 with HiFi and ultra-long reads.The command specified the HiFi and ultra-long read FASTA files.Source: §1.3 · p. 10
- Trio-binning assembly supplied maternal and paternal hapmer databases to Verkko alongside HiFi and ultra-long reads.The command used the --hap-kmers option with both parental databases and trio mode.Source: §1.3 · p. 10
- Human Hi-C assembly created an unphased Verkko graph, phased it with gfase using Hi-C reads, then reran Verkko with gfase's phasing results.The described workflow combines Verkko and gfase in three stages.Source: §1.3 · p. 10
1.4 Running with Terra using cloud computing
Human genome assemblies were run on preemptible Google Cloud Platform instances, with hifiasm (UL) split into stages. The described workflows also use parental hapmers for trio-binning and gfase-derived phasing for Hi-C assemblies.
1.4 Running with Terra using cloud computing
- Human genome assemblies used preemptible Google Cloud Platform instances, and hifiasm (UL) was divided into three steps to use them.The passage specifies that the three-step split applies to hifiasm (UL).Source: §1.4 · p. 10
- Hifiasm (UL) trio-binning proceeds through three commands, adding parental yak databases and ultra-long reads before a final run without --bin-only.The first step uses --bin-only; the second adds parental yak databases and ultra-long reads; the third retains the parental databases and ultra-long reads without --bin-only.Source: §1.4 · p. 10
- For hifiasm (UL) Hi-C assembly, the workflow starts with HiFi reads, then includes Hi-C read pairs and ultra-long reads in the final command.The final command uses --h1 and --h2 for the Hi-C read files and --ul for ultra-long reads.Source: §1.4 · p. 10
- Verkko trio-binning creates an unphased graph before adding trio phasing with Meryl hapmer databases made from parental Illumina data.The passages describe the graph-generation step, the subsequent phasing run, and the source of the hapmer databases.Source: §1.4 · p. 10
- Verkko Hi-C assembly creates an unphased graph, uses gfase with Hi-C reads for phasing, and integrates those results into Verkko through a WDL.This is the sequence described for the Hi-C phased assembly workflow.Source: §1.4 · p. 10
1.5 Running asmgene
Human assembly gene completeness was evaluated by aligning cDNAs to the CHM13v2 reference and to assembly contigs, then using paftools.js.
1.5 Running asmgene
- Human genome assembly gene completeness was evaluated with paftools.js from the minimap2 package.The procedure used paftools.js asmgene with the reference and assembly alignments.Source: §1.5 · p. 11
- The cDNAs were aligned to the CHM13v2 reference genome and assembly contigs using minimap2 version 2.24-r1122.The commands use the splice-aware high-quality preset, -cxsplice:hq.Source: §1.5 · p. 11
- The asmgene evaluation used the reference and assembly PAF alignments with -a and -i.97 options.The command was paftools.js asmgene -a -i.97.Source: §1.5 · p. 11
1.6 BUSCO
Non-human genome assemblies were assessed with BUSCO version 5.4.4 in genome mode. The lineage dataset was brassicales odb10 for Arabidopsis and solanales odb10 for potato.
1.6 BUSCO
- Non-human genome assembly evaluation used BUSCO version 5.4.4 in genome mode.The command specified the assembly FASTA, output directory, thread count, and lineage dataset.Source: §1.6 · p. 11
- Arabidopsis assemblies used the brassicales odb10 lineage dataset for BUSCO.The lineage value was supplied through the BUSCO -l option.Source: §1.6 · p. 11
- Potato assemblies used the solanales odb10 lineage dataset for BUSCO.The lineage value was supplied through the BUSCO -l option.Source: §1.6 · p. 11
1.7 Phasing accuracy evaluation
Human phasing errors were measured with yak, while potato phasing errors were assessed using haplotype-specific HiFi reads.
1.7 Phasing accuracy evaluation
- Human phasing accuracy was evaluated with yak using parental yak files and the assembly contigs.The stated command is yak trioeval.Source: §1.7 · p. 11
- Potato phasing errors were assessed using haplotype-specific HiFi reads as markers.Source: §1.7 · p. 11
1.8 Counting Telomere-to-Telomere (T2T) contigs
T2T contigs are identified by aligning assemblies to references, with the human and plant comparisons using different reference sets. The supplied passages also describe phasing-error measures and the scope of several supplementary tables.
1.8 Counting Telomere-to-Telomere (T2T) contigs
- Phasing switch error rate measures adjacent marker pairs from different haplotypes, whereas hamming error rate measures the percentage of incorrectly phased markers.Human phasing errors used parental-read 31-mers; potato errors used haplotype-specific HiFi-read markers.Source: §1.8 · pp. 12–13
- A T2T contig must align across an entire reference chromosome with telomeres at both ends; the HPRC workflow detects human T2T contigs.Human assemblies were aligned to CHM13v2, while Arabidopsis and potato assemblies were aligned to published genomes from the same datasets.Source: §1.8 · p. 11, Figure 1 · p. 13
- No HPRC Year 1 Verkko assembly had a T2T contig, while the figure also covers plant assemblies.For the plant assemblies, the reference genomes were generated from the same datasets.Source: Figure 1 · p. 13
- Supplementary Table 3 covers human dataset statistics, and Year 2 assemblies used ultra-long reads of at least 100 kb; Year 1 used a 50 kb minimum.The Year 1 minimum reflects insufficient numbers of reads at least 100 kb long.Source: Table 3 · p. 14, §1.8 · p. 14
- Supplementary Table 4 reports T2T-contig and scaffold counts for human Verkko assemblies.Source: Table 4 · p. 14