Coverage-preserving sparsification of overlap graphs for long-read assembly.

{"sci_version": "1.0", "schema": "https://corpus.bntrg.co.uk/sci/1.0/sci.schema.json", "id": "pmid:36892439", "kind": "science-record", "revision": 1, "content_hash": "sha256:e3a3e80d5495037e951a6a9ce970475e0c6c749d4563479b5480c53756b988bf", "created_at": "2026-11-01T19:01:31Z", "updated_at": "2026-11-01T19:01:31Z", "generator": {"name": "corpus-assay-engine", "run_id": "reading-sci-2026-11-01"}, "paper": {"state": "complete", "title": "Coverage-preserving sparsification of overlap graphs for long-read assembly.", "doi": "10.1093/bioinformatics/btad124", "pmid": "36892439", "authors": ["Chirag Jain"], "journal": "Bioinformatics (Oxford, England)", "year": 2023, "abstract": "MOTIVATION: Read-overlap-based graph data structures play a central role in computing de novo genome assembly. Most long-read assemblers use Myers's string graph model to sparsify overlap graphs. Graph sparsification improves assembly contiguity by removing spurious and redundant connections. However, a graph model must be coverage-preserving, i.e. it must ensure that there exist walks in the graph that spell all chromosomes, given sufficient sequencing coverage. This property becomes even more important for diploid genomes, polyploid genomes, and metagenomes where there is a risk of losing haplotype-specific information.\nRESULTS: We develop a novel theoretical framework under which the coverage-preserving properties of a graph model can be analyzed. We first prove that de Bruijn graph and overlap graph models are guaranteed to be coverage-preserving. We next show that the standard string graph model lacks this guarantee. The latter result is consistent with prior work suggesting that removal of contained reads, i.e. the reads that are substrings of other reads, can lead to coverage gaps during string graph construction. Our experiments done using simulated long reads from HG002 human diploid genome show that 50 coverage gaps are introduced on average by ignoring contained reads from nanopore datasets. To remedy this, we propose practical heuristics that are well-supported by our theoretical results and are useful to decide which contained reads should be retained to avoid coverage gaps. Our method retains a small fraction of contained reads (1-2%) and closes majority of the coverage gaps.\nAVAILABILITY AND IMPLEMENTATION: Source code is available through GitHub (https://github.com/at-cg/ContainX) and Zenodo with doi: 10.5281/zenodo.7687543.", "claims": [{"id": "claim-data-access", "statement": "Supplementary data is available at Bioinformatics online.", "kind": "methodological", "target": null, "evidence": [{"asset": "source:pmid:36892439", "locator": "sections[25] \"Supplementary data\" paragraph 2", "quote": "Supplementary data is available at Bioinformatics online."}], "state": "complete"}, {"id": "claim-target-result", "statement": "Our experiments done using simulated long reads from HG002 human diploid genome show that 50 coverage gaps are introduced on average by ignoring contained reads from nanopore datasets.", "kind": "quantitative", "target": {"value": 2.0, "unit": "per cent", "tolerance": null, "source": "Our method retains a small fraction of contained reads (1–2%) and closes majority of the coverage gaps."}, "evidence": [{"asset": "source:pmid:36892439", "locator": "sections[0] \"Abstract\" paragraph 2", "quote": "Our experiments done using simulated long reads from HG002 human diploid genome show that 50 coverage gaps are introduced on average by ignoring contained reads from nanopore datasets."}, {"asset": "source:pmid:36892439", "locator": "sections[0] \"Abstract\" paragraph 2", "quote": "Our method retains a small fraction of contained reads (1–2%) and closes majority of the coverage gaps."}], "state": "complete"}], "gaps": []}, "experiment": {"state": "partial", "objective": "Our experiments done using simulated long reads from HG002 human diploid genome show that 50 coverage gaps are introduced on average by ignoring contained reads from nanopore datasets.", "steps": [{"id": "read_published_estimate", "order": 1, "name": "Read the published estimate from the source", "kind": "other", "state": "complete", "blocked_on": null, "description": "The claim, method and evidence span published with the source article.", "duration_hours": null, "parameters": {}, "inputs": ["source:pmid:36892439"], "outputs": ["the published estimate and its evidence"], "instruments": [], "reagents": []}, {"id": "obtain_source_data", "order": 2, "name": "Obtain the source data from the named repository", "kind": "data-preparation", "state": "blocked", "blocked_on": "data:accession_absent", "description": "The GEO series accession resolves and its sample accessions are listed. This lane did not download the dataset or read its licence.", "duration_hours": null, "parameters": {}, "inputs": [], "outputs": ["the source data with its repository provenance"], "instruments": [], "reagents": []}, {"id": "run_analysis", "order": 3, "name": "Run the published analysis", "kind": "analysis", "state": "complete", "blocked_on": null, "description": "Apply the paper's statistical method to the resolved series and compare the result with the published target.", "duration_hours": null, "parameters": {}, "inputs": [], "outputs": ["the replicated result and its comparison"], "instruments": [], "reagents": []}], "materials": [], "instruments": [], "reagents": [], "conditions": {}, "gaps": ["step:obtain_source_data blocked on data:accession_absent"]}, "data": {"state": "partial", "assets": [{"id": "source:pmid:36892439", "role": "manuscript", "format": "xml", "media_type": "application/xml", "uri": "https://doi.org/10.1093/bioinformatics/btad124", "sha256": "sha256:47e94b780ed38754875b471f2d18d6d84b78f53a37cec16d705660fa14579194", "bytes": 51057, "access": "open", "state": "resolved", "reader": null, "reader_status": "reader_required", "identifier": "10.1093/bioinformatics/btad124", "version": null, "note": "Full article fetched from PMC; the checksum covers the rendered section body, not the original XML bytes.", "structure": {"pmcid": "PMC10132763", "source": "europe_pmc_fulltext", "coverage": "whole_body", "text_hash_scope": "rendered_section_body"}}], "gaps": []}, "analysis": {"state": "absent", "methods": [], "targets": [{"id": "target-published-estimate", "claim_id": "claim-target-result", "operation": null, "expected_value": 2.0, "unit": "per cent", "tolerance": null, "state": "complete", "note": "The published estimate as the reader quoted it from the paper. No tolerance is published because the paper states none."}], "gaps": ["method", "operations"]}, "capability": {"state": "complete", "requirements": [{"capability_id": "capability:computational_analysis", "label": "Computational analysis platform", "assay_families": ["meta_analysis", "machine_learning", "survival_analysis", "statistical_regression", "pca", "molecular_docking", "network_analysis", "differential_expression", "gwas"], "availability_state": "owned", "tier_unlocked": "R1", "candidate": "Automated Assays Laravel application and simulated adapters"}], "gaps": []}, "readiness": {"state": "blocked", "tier": "R4", "blocking_axis": "data", "blocked_on": "data:accession_absent", "axes": {"method": {"tier": "R4", "expressible": false, "required_operations": [], "missing_operations": [], "basis": "The reader quoted the method the paper names (not named), but the corpus's method extractor could not map it onto a DSL operation, so the method is published but not expressible."}, "capability": {"tier": "R1", "capability_id": "capability:computational_analysis", "availability_state": "owned", "basis": "The computational analysis is owned. The physical bench the paper used is not, so a physical validation cannot be run here."}, "data": {"tier": "R4", "reachable": false, "accessions": [], "resolved_accessions": [], "statements": ["Supplementary data is available at Bioinformatics online."], "basis": "The paper names no accession to its source data, so the data has to come from the authors."}}, "can_run": {"dsl_operations": [], "assets": ["source:pmid:36892439"], "steps": ["run_analysis"]}, "must_build": {"dsl_operations": [], "converters": [], "readers": [], "capabilities": [], "data_gaps": ["data:geo:None"]}, "gaps": ["data:accession_absent"]}, "review": {"state": "partial", "machine_critique": {"kind": "extraction_review", "reader": {"model": "MiniMax-M3.1-Flash", "provider": "minimax", "provider_family": "minimax", "read_at": "2026-11-01T18:32:59Z", "independence": "single_reader"}, "evidence_check": {"method": null, "availability": "verbatim"}, "calls": 5, "usage": {"prompt_tokens": 14285, "completion_tokens": 1900, "cached_tokens": 128}}, "human_critique": null, "stages": [{"id": "extraction", "state": "complete", "reader": "MiniMax-M3.1-Flash", "provider": "minimax"}], "gaps": ["review.independent_reader", "review.machine_critique", "review.human_critique"]}, "execution": {"state": "absent", "status": "not_run", "mode": null, "runs": [], "gaps": ["execution.not_run"]}, "provenance": {"entities": [{"id": "pmid:36892439", "type": "paper", "label": "pmid:36892439"}, {"id": "source:pmid:36892439", "type": "manuscript", "label": "PMID 36892439 full text"}, {"id": "data:geo:None", "type": "dataset", "label": "GEO None"}], "activities": [{"id": "activity-reading-sci-2026-11-01", "type": "classification", "used": [{"id": "pmid:36892439", "type": "paper", "label": "pmid:36892439"}, {"id": "source:pmid:36892439", "type": "manuscript", "label": "PMID 36892439 full text"}, {"id": "data:geo:None", "type": "dataset", "label": "GEO None"}], "agent": "agent:corpus-assay-engine"}, {"id": "activity-read-36892439", "type": "extraction", "used": ["source:pmid:36892439"], "agent": "agent:minimax-reader"}, {"id": "activity-resolve-None", "type": "accession_resolution", "used": ["data:geo:None"], "agent": "agent:corpus-assay-engine"}], "agents": [{"id": "agent:corpus-assay-engine", "type": "software", "label": "Corpus assay engine"}, {"id": "agent:minimax-reader", "type": "software", "label": "MiniMax literature reader"}], "source_run_id": "reading-sci-2026-11-01", "dsl_catalogue_fingerprint": "343fb30756ba6ec3", "capability_table_fingerprint": "2cb3e42f047d2ecf", "snapshot_id": "ba34b49490d9bfaf"}, "lineage": {"parent_id": null, "parent_hash": null, "fork_of": null, "generation": 0}, "gaps": ["execution.not_run", "method", "operations", "review.human_critique", "review.independent_reader", "review.machine_critique", "step:obtain_source_data blocked on data:accession_absent"]}