Reconstructing Biological Sequences through Graph Traversal

50 concepts46 papers1 proposal

The fundamental challenge of genomic sequencing is a physical one: modern sequencing technologies cannot read a chromosome or an RNA transcript from end to end. Instead, they generate millions of short, fragmented, and often error-prone snippets called "reads." Reconstructing the original biological sequence from these fragments is one of the foundational computational problems in bioinformatics.

The most intuitive formulation of this problem is the Shortest Common Superstring (SCS) problem: find the shortest single string that contains every read as a substring. In early theoretical work, Jiang et al. proved in Linear approximation of shortest superstrings that while finding the absolute optimal superstring is NP-hard, a simple greedy algorithm that iteratively merges the highest-overlapping reads provides a reliable constant-factor approximation.

However, real biological sequences are rarely simple strings. Genomes are riddled with massive, identical repeat regions; viral populations exist as mixtures of highly similar variants called quasispecies; and a single eukaryotic gene can produce dozens of distinct RNA molecules through alternative splicing. In these scenarios, linear string matching breaks down.

To overcome these challenges, modern bioinformatics shifts the paradigm from linear string manipulation to graph theory. By representing sequence fragments as nodes and their valid biological overlaps as edges, the messy combinatorial search for a sequence is transformed into an elegant, structured problem of pathfinding and optimization.


De Bruijn Graphs: Resolving Scale via Substring Overlaps

When dealing with billions of short reads, comparing every read against every other read to find overlaps is computationally prohibitive. The de Bruijn graph solves this by breaking reads down into even smaller, fixed-length substrings of length $k$, known as $k$-mers.

In a de Bruijn graph, nodes represent prefixes or suffixes of length $k-1$, and directed edges represent the observed $k$-mers that connect them. The beauty of this representation is that identical sequences automatically collapse into the same nodes and edges, naturally compressing the data and highlighting shared structures. Reconstructing the original sequence then becomes a matter of finding a path that traverses the graph.

Reads: ATCGG, TCGGT
3-mers (k=3): ATC, TCG, CGG, GGT

Graph Construction:
[AT] --(ATC)--> [TC] --(TCG)--> [CG] --(CGG)--> [GG] --(GGT)--> [GT]

This reference-free strategy allows assemblers to reconstruct complex genetic structures from scratch. For instance, Song et al. demonstrated in Correction: An Improvement of Shotgun Proteomics Analysis by Adding Next-Generation Sequencing Transcriptome Data in Orange how de Bruijn graphs can assemble uncharacterized transcriptomes to build custom protein databases for non-model organisms. Similarly, Mehr et al. used multi-$k$-mer de Bruijn graphs in Transcriptome deep-sequencing and clustering of expressed isoforms from Favia corals to optimize the trade-off between sequence continuity and the sensitivity needed to capture rare transcripts. In genome surveys, such as the work on the marbled rockfish by Song et al. in Whole genome survey analysis and microsatellite motif identification of Sebastiscus marmoratus, this graph structure serves as the initial step to build longer contiguous sequences (contigs).

The primary challenge of de Bruijn graph assembly is ambiguity: when a $k$-mer appears in multiple places in a genome, it creates a "fork" or a loop in the graph, leading to multiple valid traversals. In Fundamental Limits of Multiple Sequence Reconstruction from Substrings, Levick et al. mathematically defined the exact boundaries of this ambiguity. The authors proved that unique reconstruction depends not on having entirely unique $k$-mers, but on whether the global graph topology prevents alternative, valid path decompositions. When these conditions are met, algorithms like the one proposed by Wang et al. in SeedsGraph: an efficient assembler for next-generation sequencing data can reliably find Eulerian paths—paths that visit every edge exactly once—to output accurate contigs.


Directed Acyclic Graphs: Finding Optimal Paths

When biological sequences have a clear linear order or are mapped against a known reference backbone, the relationships between fragments can be structured as a Directed Acyclic Graph (DAG). Because DAGs have a strict topological ordering, researchers can use highly efficient dynamic programming and shortest-path algorithms to find optimal sequences out of billions of possibilities.

Consider the task of gene finding or sequence alignment. Local alignment tools like BLAST often produce a disjointed "soup" of high-scoring pairs. In genBlastA: Enabling BLAST to identify homologous gene sequences, She et al. modeled these fragmented hits as nodes in a DAG. Edges were drawn only between fragments that maintained a biologically plausible linear order and colinearity with a reference sequence. By running a shortest-path algorithm on this network, the authors successfully stitched fragmented hits into coherent, full-length candidate genes.

[BLAST Hit 1] ----> [BLAST Hit 2] ----> [BLAST Hit 3]  (Valid Path)
      \                                      ^
       \------------------------------------/  (Alternative Transition)

This DAG-based pathfinding framework is highly versatile and appears across several distinct genomic domains:


Splicing Graphs and Network Flows: Disentangling Isoforms

As the ENCODE project famously revealed, the classic "one gene, one protein" model is an oversimplification. As Bruce et al. discussed in What is a gene, post-ENCODE? History and updated definition, a single gene is actually a union of genomic sequences that encode a coherent set of overlapping functional products, largely due to alternative splicing.

To map this complexity, transcriptomics relies on splicing graphs. In these graphs, nodes represent exons (expressed sequence blocks) and edges represent splice junctions (how exons are glued together).

Alternative Splicing Graph:
      /--> [Exon 2] --\
[Exon 1]               --> [Exon 4]  (Isoform A: 1-2-4)
      \--> [Exon 3] --/              (Isoform B: 1-3-4)

By mapping RNA-seq reads to these graphs, researchers can systematically identify variations like exon skipping and intron retention across different species and diseases, as seen in studies by Ong (Genome-wide analysis of alternative splicing in Volvox carteri), Ramani et al. (Genome-wide analysis of alternative splicing in Caenorhabditis elegans), and Kahles et al. (Integrative Genome-wide Analysis of the Determinants of RNA Splicing in Kidney Renal Clear Cell Carcinoma).

However, knowing the possible paths through a splicing graph is only half the battle; we must also figure out which paths are actually being expressed and in what quantities. This creates a classic optimization challenge.

To solve this, Mezlini et al. developed iReckon: Simultaneous isoform discovery and abundance estimation from RNA-seq data, which builds a massive library of potential paths from a splicing graph and uses read-mapping density to simultaneously discover isoforms and estimate their abundances.

Taking this a step further, Mao et al. framed transcriptome assembly as a sparse flow decomposition problem in RefShannon: A genome-guided transcriptome assembler using sparse flow decomposition. Here, the number of sequencing reads covering an exon or junction is treated as a mathematical "flow" through a network. Because biology is generally parsimonious, the goal is to decompose this total network flow into the minimum number of individual paths (isoforms) that can mathematically account for the observed read counts.

A similar parsimony principle applies to tracking viral evolution. In Viral Population Estimation Using Pyrosequencing, Eriksson et al. reconstructed viral quasispecies by modeling overlapping reads as a DAG. They applied Dilworth’s Theorem—a fundamental graph theorem stating that the size of the minimum path cover equals the size of the maximum antichain—to find the minimum number of viral strains needed to explain a patient's entire pool of sequencing data.


Graph Partitioning: Taming Complexity through Clustering

Sometimes, a sequence graph is too massive, noisy, or interconnected to traverse directly. In these cases, the solution is to partition the graph into smaller, isolated subgraphs before attempting path reconstruction.

For example, assembling a massive genome can easily overwhelm a computer's memory. In TIGER: tiled iterative genome assembler, Wu et al. solved this by organizing intermediate assembly fragments into a connectivity graph based on shared sequence overlaps. They then applied graph partitioning algorithms to break this massive network into independent "tiles," allowing for targeted, parallel assembly on standard hardware.

Graph partitioning is also essential for separating mixed biological signals:

  • Metagenomics: Environmental samples contain a mixture of hundreds of different microbial species. In GraphBin: refined binning of metagenomic contigs using assembly graphs, Mallawaarachchi et al. demonstrated that instead of looking at sequences in isolation, we can use the topology of the assembly graph itself. By drawing edges between contigs that are spanned by paired-end reads, they used graph connectivity to group related contigs into clean, species-specific genomic bins.
  • Polyploid Haplotype Assembly: Organisms with multiple copies of chromosomes (like humans or polyploid plants) present a major challenge: distinguishing between nearly identical maternal and paternal chromosomes. In SDhaP: haplotype assembly for diploids and polyploids via semi-definite programming, Das framed this as a correlation clustering task. Reads are represented as nodes, and edges are weighted by how much the overlapping fragments agree or disagree. The algorithm then partitions the graph into distinct clusters, effectively separating the chromosomes.
  • Scaffold Orientation: Even when sequences are assembled into long fragments (scaffolds), determining their correct physical orientation remains a challenge. As Avdeyev showed in Orienting Ordered Scaffolds: Complexity and Algorithms, modeling these fragments as a scaffold graph with adjacency and orientation constraints allows graph algorithms to resolve structural conflicts and finalize the linear genome structure.

By moving away from simple string matching and embracing graph theory, bioinformatics transforms the chaotic reality of biological data—repeats, alternative splicing, errors, and mixed populations—into structured networks where biological truth can be uncovered through mathematical optimization.

Key Foundational Work

Linear approximation of shortest superstrings (1991) — contributed 1 concept elements to this direction.
Shuffling biological sequencess with motifs constraints (2004) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_graph_based_sequence_assembly_491026d8,
  title = {graph-based sequence assembly},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-sequence-assembly/rdr_491026d8270d4fe98425c6e3da5f95c1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_graph_based_sequence_assembly_491026d8_v1,
  title = {graph-based sequence assembly},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/graph-based-sequence-assembly/rdr_491026d8270d4fe98425c6e3da5f95c1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake