On the Readability of Overlap Digraphs

Rayan Chikhi, Paul Medvedev, Martin Milanic, Sofya Raskhodnikova

TL;DR

This paper introduces "readability" as a graph parameter representing the minimum string length needed to construct an overlap digraph. They develop graph-theoretic characterizations for readability, providing bounds and exact values for specific graph classes like trees and C4-free graphs, and explore its asymptotic behavior for general graphs.

What Problem Does This Paper Address?

The paper tackles a problem rooted in bioinformatics, specifically genome assembly. In this context, short DNA fragments (reads) are used to reconstruct a larger genome. Overlap graphs are a key tool, where vertices represent reads and edges signify overlaps. The "readability" of such a graph is crucial: it quantifies the minimum length of the original DNA fragments required to form the observed overlap structure. If fragments are too short, the overlap graph might not accurately reflect the true genome structure, making assembly difficult or impossible. While it's known that any directed graph can be represented as an overlap graph, the string lengths required can be exponentially large, which is impractical. This paper aims to understand and bound this minimum string length (readability) in terms of graph properties, moving away from string-based definitions to more general graph-theoretic ones.

Methods

The core of the paper is the translation of the string-based "readability" concept into purely graph-theoretic terms. They achieve this by defining "decompositions" of graphs, which are essentially assignments of weights to edges.

  • Overlap Labeling and Decomposition: An overlap labeling of a graph assigns strings to vertices such that edges correspond to proper overlaps. The "l-decomposition" is derived from such a labeling by assigning an edge weight equal to the overlap length.
  • P4-Rule and Strict P4-Rule: For trees, they introduce the "P4-rule," a condition on edge weights of induced paths of length 3 (P4s). If the middle edge has the maximum weight, it must be greater than or equal to the sum of the weights of the adjacent edges. For C4-free graphs, a stricter version, the "strict P4-rule," is used.
  • HUB-Rule: For general bipartite graphs, they define the "HUB-rule," which relates disjoint unions of bicliques and the behavior of twins across different levels of decomposition.
  • Constructive Labeling: They develop algorithms to construct overlap labelings from decompositions satisfying these rules, which is key to proving their bounds.
  • Asymptotic Analysis: They analyze the behavior of readability as the number of vertices grows, using counting arguments and specific graph constructions.

Datasets

Not discussed in the paper. The paper focuses on theoretical graph properties and does not use empirical datasets.

Key Insights and Ideas

  • Readability as a Graph Parameter: The paper successfully reframes a string-based problem (overlap graph construction) into a purely graph-theoretic one, making it amenable to standard graph analysis techniques.
  • P4-Rule for Trees: The characterization of tree readability via the P4-rule is elegant. It shows that local conditions on induced paths can precisely determine the global property of minimum string length.
  • HUB-Rule and Readability Connection: The HUB-rule provides a graph-theoretic parameter (HUB number) that is closely related to readability for bipartite graphs, offering a way to bound it.
  • Asymptotic Lower Bounds: The finding that almost all graphs have readability of at least $\Omega(n/\log n)$ is significant, suggesting that complex overlap structures are common.
  • Sharp Bounds for Trees: The result that readability of a tree is bounded by its radius, and that this bound is sharp, is a precise and satisfying characterization.

Key Results

  • Trees: Readability of a tree $T$ is exactly equal to the minimum $k$ such that there exists a decomposition of size $k$ satisfying the P4-rule. For every $k > 0$, there exists a tree $T$ with $r(T) = \text{radius}(T) = k$.
  • C4-free Bipartite Graphs: Readability $r(G)$ is bounded by $t/2 < r(G) < t$, where $t$ is the minimum size of a decomposition satisfying the strict P4-rule.
  • Bipartite Graphs: The HUB number, $hub(G)$, satisfies $hub(G) \le r(G) \le 2hub(G) - 1$.
  • General Graphs: Almost all graphs in $B_{n \times n}$ (balanced bipartite graphs) and $D_n$ (digraphs) have readability $\Omega(n/\log n)$.
  • Specific Graph Family ($H_k$): A constructed graph family $H_k$ has readability $\Omega(n)$, where $n$ is the number of vertices.

Limitations and Future Work

  • General Graphs Gap: While the HUB number provides a bound for general bipartite graphs, it doesn't perfectly capture readability. The paper notes that the upper bound $2hub(G)-1$ leaves a gap, and finding tighter characterizations for general graphs is an open direction.
  • Complexity: The paper raises the question of whether computing readability for a general digraph is NP-hard, which remains unexplored.
  • Exponential Readability: The authors conjecture that graphs with exponential readability exist and pose this as a major open question.
  • Bioinformatics Relevance: Further study into graphs with poly-logarithmic readability is suggested, as this aligns with practical constraints in bioinformatics where read lengths are often poly-logarithmic in the number of reads.

Summary updated

Abstract

We introduce the graph parameter readability and study it as a function of the number of vertices in a graph. Given a digraph \(D\), an injective overlap labeling assigns a unique string to each vertex such that there is an arc from \(x\) to \(y\) if and only if \(x\) properly overlaps \(y\). The readability of \(D\) is the minimum string length for which an injective overlap labeling exists. In applications that utilize overlap digraphs (e.g., in bioinformatics), readability reflects the length of the strings from which the overlap digraph is constructed. We study the asymptotic behaviour of readability by casting it in purely graph theoretic terms (without any reference to strings). We prove upper and lower bounds on readability for certain graph families and general graphs.
BibTeX
@inproceedings{chikhi2015readability,
  author = {Rayan Chikhi and Paul Medvedev and Martin Milanic and Sofya Raskhodnikova},
  title = {{On the Readability of Overlap Digraphs}},
  booktitle = {Discret. Appl. Math},
  year = {2015},
  url = {https://openreview.net/forum?id=Oq185F0gZ7},
}

Loading related content...

Figure