Source-linked AI summary
Sibelia: A scalable and comprehensive synteny block generation tool for closely related microbial genomes
Ilya Minkin, Anand Patel, Mikhail Kolmogorov, Nikolay Vyahhi, Son Pham
TL;DR
Comparisons within microbial species matter for studying genomic diversity, but current tools face limits in scale and in representing blocks at multiple resolutions. Sibelia iteratively builds de Bruijn graphs to find repeated and shared synteny blocks in a hierarchy. It reports fast analyses of dozens of genomes and identifies within-genome repeats that other tested tools miss.
Problem
Comparative analysis within microbial species matters for understanding microbial diversity, while many tools struggle with large genome sets and do not represent synteny blocks at multiple resolutions.
Source: §1 · pp. 1, 3Method
Sibelia iteratively constructs de Bruijn graphs at different k values to find synteny blocks and represent them hierarchically.
Source: §1 · p. 3Results
Sibelia finds synteny blocks repeated within genomes and shared across genomes, analyzing 31 S. aureus genomes in 31 minutes and 59 E. coli genomes in 107 minutes on a standard desktop.
Source: §1 · p. 3Takeaways & Limitations
Sibelia’s hierarchical representation lets users explore synteny-block composition at multiple scales, including finer blocks such as insertion elements.
Source: §3 · p. 10, §4 · p. 12The paper classifies construction as unsuccessful when total synteny-block coverage is below 40% for a set of same-species genomes.
Source: §2.3 · p. 7
Abstract
from arXiv · showhide
Comparing strains within the same microbial species has proven effective in the identification of genes and genomic regions responsible for virulence, as well as in the diagnosis and treatment of infectious diseases. In this paper, we present Sibelia, a tool for finding synteny blocks in multiple closely related microbial genomes using iterative de Bruijn graphs. Unlike most other tools, Sibelia can find synteny blocks that are repeated within genomes as well as blocks shared by multiple genomes. It represents synteny blocks in a hierarchy structure with multiple layers, each of which representing a different granularity level. Sibelia has been designed to work efficiently with a large number of microbial genomes; it finds synteny blocks in 31 S. aureus genomes within 31 minutes and in 59 E.coli genomes within 107 minutes on a standard desktop. Sibelia software is distributed under the GNU GPL v2 license and is available at: https://github.com/bioinf/Sibelia Sibelia's web-server is available at: http://etool.me/software/sibelia
1 Introduction
Comparative analysis within microbial species matters for understanding virulence, disease, and genomic diversity, but available approaches face scale and resolution challenges. Sibelia uses iterative de Bruijn graphs to identify repeated and shared synteny blocks and organize them hierarchically.
1 Introduction
- Comparing strains within a species has become important as outbreaks of virulent microbes and multidrug-resistant strains intensify efforts to understand microbial diversity.Examples include E. coli O157:H7, TB, and MRSA.Source: §1 · p. 1
- Synteny blocks support structural-variation analysis and genome-rearrangement software, while conserved regions can help infer the minimum genomic material required for bacterial life.The paper connects the latter use to the Minimal Genome Project.Source: §1 · p. 1
- Tools face scaling costs from pairwise genome alignments, parameter-dependent block granularity, and the need to process large volumes of unannotated nucleotide sequences.Applications differ in the scales they need, from large blocks for ancestral reconstruction to small and large blocks for virulence-factor analysis.Source: §1 · p. 2
- DRIMM-Synteny uses gene-alphabet genomes and does not present blocks at multiple granularity levels, limiting its fit for large sets of raw bacterial sequences.Its approach avoids threading by modifying the sequence so the resulting graph reveals synteny blocks as non-branching paths.Source: §1 · pp. 2–3
- A single de Bruijn graph does not capture virtual genomes’ multiscale, multigranular repeat structure, motivating an iterative approach with graphs built at different k values.The approach constructs hierarchical synteny blocks whose layers represent different granularity levels.Source: §1 · p. 3
- Sibelia identifies synteny blocks repeated within genomes and shared across genomes, then represents them at multiple granularity levels.It analyzes 31 S. aureus genomes in 31 minutes and 59 E. coli genomes in 107 minutes on a standard desktop.Source: §1 · p. 3
2 Methods
The methods treat concatenated genomes as a virtual genome and seek repeated blocks within it. Sibelia iteratively simplifies de Bruijn graphs at increasing k values, then retraces the decompositions to represent blocks at multiple scales.
2.1 De Bruijn Graph and Cycles
- De Bruijn graphs encode k-mers as vertices and connect consecutive k-mers; repeated regions can appear as paths, while short cycles can obscure repeats.Bulges arise from mismatches or indels, and loops from nearby repeated k-mers; Sibelia removes bulges by sequence modification and uses larger k to resolve small loops.Source: §2.1 · p. 4
- The sequence-modification heuristic removes a bulge by substituting one repeat instance for another, turning inexact repeats into exact repeats in the modified sequence.The paper formulates bulge removal as finding a minimum-edit-distance sequence whose graph lacks two-way cycles shorter than a threshold, but uses a heuristic because the problem’s complexity is unknown.Source: §2.1 · pp. 4–5
2.2 Effects of k-Mer Size and Bulge Removal Procedure in Repeat Decomposition
- Different k values expose repeats at different scales, while bulge simplification can merge consecutive non-branching paths and enable decomposition across graph stages.A path revealed at larger k can be decomposed into smaller paths from a graph built with smaller k.Source: §2.2 · pp. 5–6
2.3 Hierarchical Representation of Synteny Blocks
- Sibelia starts with small k and a short bulge threshold, simplifies the sequence, then increases k until large-scale blocks appear; prior-stage decompositions recover finer blocks.Its resulting hierarchy represents each final-stage non-branching path as a tree whose children are decompositions from earlier stages and whose leaves come from the smallest k stage.Source: §2.2 · pp. 6–7, §2.3 · p. 7
- The first-stage k and bulge threshold most strongly determine reconstruction, while later-stage parameters control block size and granularity.The paper derives the default first-stage pair as (30, 150) and gives four default stages; users can add intermediate stages for a smoother decomposition.Source: §2.3 · pp. 7–8
- The authors classify construction as unsuccessful when total synteny-block coverage is below 40% for a set of genomes within one species.The paper presents this threshold in relation to its core-genome analysis criterion.Source: §2.3 · p. 7
3 Results
Sibelia identifies synteny blocks, including within-genome repeats, and represents them at multiple scales. In simulated and real-genome comparisons, it captures blocks missed by other tools and shows a runtime advantage on larger datasets.
3 Results
- Sibelia correctly identified all simulated synteny blocks; no other tool located within-genome blocks 4 and 5, and only Mauve detected shared repeats with multiplicity greater than 2.The test used two hypothetical 120-kbp genomes, with 20-kbp blocks and a 3% mutation probability per position.Source: §3 · pp. 9–10
- With 1,500-bp insertion elements, Sibelia's hierarchy separates large-scale blocks inside from finer blocks outside, supporting application-dependent choices of scale.The inserted sequences were mutated at 3% per instance.Source: §3 · p. 10
3.1 Comparing Sibelia with Existing Tools
- On E.coli-3, Sibelia, Mauve, and Mugsy decompositions were similar, while Multiz was more fragmented; Sibelia's finest stage resembled Multiz.The figure places Mauve, Mugsy, Sibelia's last stage, Multiz, and Sibelia's first stage from inside to outside.Source: §3.1 · pp. 10–11, Figure 5 · p. 12
- Across stages, blocks merge into longer synteny blocks, and a final-stage block is decomposed into a multilayer tree.The figure illustrates this iterative construction for Helicobacter pylori strains F32 and Gambia94/24.Source: Figure 4 · p. 11
- 7 times faster than Mugsy and Multiz on E.coli-59; shared blocks covered 66.95% and 54.25% of average genome size in E.coli-59 and S.aureus-31.Sibelia's memory use was similar to Mugsy and Mauve, but worse than Multiz. Benchmarks also used E.coli-3 for block-generation quality and larger datasets for runtime and memory comparisons.Source: §3.1 · pp. 10–11, Table 2 · p. 12
4 Discussion
Sibelia uses iterative de Bruijn graphs to represent synteny blocks hierarchically for large numbers of same-species microbial genomes. The discussion distinguishes this decomposition from Cactus graphs and identifies multiscale genome rearrangement and evolution studies as a future direction.
4 Discussion
- Sibelia uses iterative de Bruijn graphs to represent synteny blocks hierarchically, allowing users to explore their composition.Source: §4 · p. 12
- Its block-decomposition algorithm differs from the nested structure of Cactus graphs; the relationship between the approaches remains for future study.Source: §4 · p. 12
- The authors identify studying genome rearrangement and evolution with multiple levels of synteny blocks as a future research direction.Source: §4 · p. 12
6 Appendix
The appendix relates microbial species similarity to exact-match runs and uses their lengths to set graph simplification thresholds across k values.
6.1 Microbial Species And The Choice of k
- Under the pragmatic definition, same-species isolates have DDH >70%, corresponding to approximately 95% average nucleotide identity and a 5% mutation chance per conserved position.Source: §6.1 · p. 13
- Exact-match segments longer than k are gluing segments; consecutive gluing segments delimit bulges, whose intervening branches and distances characterize bulge structure.Source: §6.1 · p. 13
- P{l = k} = (1 − ρ)^kρ and P{l ≥ k} = (1 − ρ)^k describe exact-match run lengths; d(k) sets the bulge-length simplification threshold for each k.Source: §6.1 · p. 13
- Fig. 6 contrasts a genome sequence with its de Bruijn graph and C-Graph at k = 3.Source: Figure 6 · p. 13
7 Hierarchy Representation of Synteny Blocks
This section defines C-Graphs and relates non-branching paths in graphs built with different k values, establishing how those paths connect across parameter choices.
7.1 Parameter k in repeats reconstruction
- The C-Graph construction represents a string as consecutive position vertices joined by edges, then glues positions under a k-dependent rule.Source: §7.1 · p. 14
- C-Graphs modify de Bruijn gluing at repeat boundaries and use single-character vertex labels to avoid overlapping synteny blocks at shared branching vertices.Source: §7.1 · p. 14
- For k0 < k1, a non-branching path between branching vertices in the k1 de Bruijn graph corresponds to a path between branching vertices in the k0 graph, though it need not remain non-branching.Source: §7.1 · p. 14
- At lower k, positions glued at higher k remain glued, so differing neighboring characters preserve branching at the path endpoints.Source: §7.1 · p. 14