On the Sound Covering Cycle Problem in Paired de Bruijn Graphs

Christian Komusiewicz, Andreea RadulescuFAW 2015 · DOI

TL;DR

This paper introduces and tackles the "Sound Covering Cycle" problem, a crucial challenge in de novo genome assembly using paired-end sequencing data. The authors present the first exact algorithms for this problem, offering a significant step towards more accurate and efficient genome reconstruction.

What Problem Does This Paper Address?

Genome assembly, the process of reconstructing a complete DNA sequence from fragmented reads, is a complex task. Modern sequencing technologies generate billions of short, often erroneous, reads. A key challenge arises from repetitive regions in the genome, which can be longer than the reads themselves, making it difficult to distinguish between different occurrences of the same sequence.

To overcome this, researchers use "paired-end reads," which consist of two reads from opposite ends of a DNA fragment, separated by a known "insert length." This information helps span longer repeats. De Bruijn graphs are a standard tool for genome assembly, where nodes represent k-mers (substrings of length k) and edges represent overlaps. However, incorporating paired-end information directly into these graphs, creating "paired de Bruijn graphs," leads to more complex computational problems.

This paper focuses on the "Sound Covering Cycle" problem within these paired de Bruijn graphs. The goal is to find a specific type of cycle in the graph that represents the entire genome. This cycle must be "covering" (meaning it traverses every possible overlap represented by the graph's edges) and "sound" (meaning the paired-end information from the reads is consistent with the cycle's structure and the known insert length). Finding such a cycle is essential for accurate genome reconstruction, especially in organisms with circular chromosomes.

Methods

The paper's core contribution is the development of the first exact algorithms for the Sound Covering Cycle problem. They tackle this by:

  • Defining the Problem Formally: They precisely define "covering" and "sound" cycles in the context of paired de Bruijn graphs, linking them to the biological constraints of genome assembly.
  • Cycle-Walk Decomposition: A key technique is decomposing any walk or cycle into a sequence of maximal simple walks and connecting walks. This structured representation simplifies analysis and algorithm design.
  • "Walk Graph" Construction: For the main algorithm, they construct a new graph called a "walk graph." In this graph, each vertex represents a walk of length d (the insert size) in the original paired de Bruijn graph. Edges connect these walks if they can be sequentially combined while maintaining the "soundness" property.
  • Dynamic Programming: A dynamic programming approach is used on the walk graph to find candidate walks that cover a significant portion of the genome and satisfy certain soundness criteria.
  • Money Changing Reduction: The problem of finding a cycle of a specific length is reduced to a variation of the "money changing" problem, a well-studied combinatorial problem.
  • Algorithm for Variants: The paper also extends these techniques to address related problems, such as finding the shortest sound covering cycle and dealing with approximately sound cycles (where the insert length might not be exact or there might be some errors).

Datasets

Not discussed in the paper. The paper focuses on theoretical algorithms and their complexity, rather than empirical evaluation on specific biological datasets.

Key Insights and Ideas

  • The "Soundness" Constraint is Key: The paper highlights that simply finding a covering cycle isn't enough; it must also be "sound" with respect to the paired-end read information. This biological constraint is what makes the problem challenging and unique.
  • Decomposition Simplifies Complexity: The cycle-walk decomposition is a powerful abstraction that breaks down a complex cycle into manageable components, making it easier to reason about and build algorithms.
  • Walks as Vertices: The novel idea of constructing a "walk graph" where vertices represent entire walks of length d is a clever way to manage the complexity introduced by the insert size constraint. This allows for a more efficient search for valid cycles.
  • Bridging Theory and Practice: By formalizing the Sound Covering Cycle problem and developing exact algorithms, the paper provides a theoretical foundation for improving de novo genome assembly, particularly for organisms with circular genomes.

Key Results

The paper presents several theoretical results, primarily focused on algorithmic complexity:

  • NP-Hardness: The Sound Covering Cycle problem is shown to be NP-hard, meaning that finding a solution is computationally difficult for large inputs.
  • Exact Algorithms: The authors provide the first exact algorithms for the Sound Covering Cycle problem, with running times that are exponential in the number of vertices (n) and the insert size (d), but polynomial in the graph's size and the desired cycle length (l). Specifically, one algorithm runs in O(8n·Δ·2^n) · poly(n + log l) time, where Δ is the maximum outdegree of the graph.
  • Algorithms for Variants: They also present algorithms for related problems:
  • Shortest Sound Covering Cycle: Solvable in O(n^4 · d · Δ^(3d)) time.
  • Approximately Sound Covering Cycle: Solvable in O(8n·Δ·2^nd) poly(n·Δ^d + log l) time.
  • Tractable Special Case: A special case where the "compatibility graph" of the paired de Bruijn graph is a union of loops can be solved in polynomial time, O(8n·Δ·2^n)· poly(n + log l).

Limitations and Future Work

  • Exponential Complexity: The presented exact algorithms have exponential dependencies on n and d, which can be prohibitive for very large genomes or large insert sizes.
  • Enumeration of Walks: A significant bottleneck in the algorithms is the enumeration of all walks of length d. Future work could focus on avoiding this explicit enumeration for substantial improvements.
  • Open Problems: The paper notes that it is still an open question whether finding a fixed-length covering cycle (without the "soundness" constraint) can be solved in polynomial time.
  • Extending Tractable Cases: The authors suggest exploring extensions to the tractable special case, such as when every vertex in the compatibility graph has an outdegree of one.

Summary updated

BibTeX
@inproceedings{komusiewicz2015sound,
  author = {Christian Komusiewicz and Andreea Radulescu},
  title = {{On the Sound Covering Cycle Problem in Paired de Bruijn Graphs}},
  booktitle = {FAW},
  year = {2015},
  doi = {10.1007/978-3-319-19647-3\_14},
}

Loading related content...

Figure