Abstract
RNA-seq has made feasible the analysis of a whole set of expressed mRNAs. Mapping-based assembly of RNA-seq reads sometimes is infeasible due to lack of high-quality references. However, de novo assembly is very challenging due to uneven expression levels among transcripts and also the read coverage variation within a single transcript. Existing methods either apply de Bruijn graphs of single-sized k-mers to assemble the full set of transcripts, or conduct multiple runs of assembly, but still apply graphs of single-sized k-mers at each run. However, a single k-mer size is not suitable for all the regions of the transcripts with varied coverage. This paper presents a de novo assembler Bermuda with new insights for handling uneven coverage. Opposed to existing methods that use a single k-mer size for all the transcripts in each run of assembly, Bermuda self-adaptively uses a few k-mer sizes to assemble different regions of a single transcript according to their local coverage. As such, Bermuda can deal with uneven expression levels and coverage not only among transcripts, but also within a single transcript. Extensive tests show that Bermuda outperforms popular de novo assemblers in reconstructing unevenly-expressed transcripts with longer length, better contiguity and lower redundancy. Further, Bermuda is computationally efficient with moderate memory consumption.
Introduction: The Challenge of Uneven Coverage
The primary goal of transcriptomics is to reconstruct the full set of expressed mRNAs from raw RNA-seq reads. While mapping-based assembly is effective when a high-quality reference genome is available, many organisms lack such resources, necessitating de novo assembly. This process is inherently difficult due to uneven coverage.
Uneven coverage manifests in two ways: variation in expression levels between different genes and stochastic variation in read density within a single transcript. This creates a "Goldilocks" dilemma for traditional assemblers using fixed k-mer sizes. Large k-mers provide high specificity but fail to bridge low-coverage "valleys," leading to fragmented assemblies. Conversely, small k-mers can bridge these gaps but often introduce "tangles" and cycles in the de Bruijn graph, resulting in chimeric or false transcripts.
Methods: Adaptive and Bidirectional Assembly
Bermuda addresses these challenges by introducing a transcript-level dynamic strategy. Instead of a fixed k-mer size, it self-adaptively switches between multiple k-mer sizes based on local coverage.
1. Multi-k Error Correction
Bermuda first constructs four de Bruijn graphs with decreasing k-mer sizes (e.g., k=30, 25, 20, 15). It uses these graphs to iteratively "polish" raw reads, starting with the most specific (largest k) and moving to smaller k-mers to correct errors in lowly-expressed regions.
2. Bidirectional Fragment Construction
The core of Bermuda is its bidirectional growth algorithm. Starting from a seed read, it extends the fragment in both 5’ to 3’ and 3’ to 5’ directions.
- Adaptive k-selection: Bermuda attempts to use the largest possible k-mer for the current local coverage. If a path is blocked due to low coverage, it automatically drops to a smaller k-mer size to find a valid connection.
- Direct Joining: Rather than purely traversing a graph, Bermuda uses the graph to identify overlapping reads and joins them directly, which significantly reduces the risk of following chimeric paths.
3. Splicing Graph Construction
Finally, these high-quality fragments are linked into splicing graphs. Bermuda employs the Oases traversal algorithm to identify various isoforms, effectively handling alternative splicing.
Results and Benchmarking
Bermuda was benchmarked against industry standards—Trinity, Oases-M, IDBA-Tran, and SOAPdenovo-Trans—using real-world datasets from Human, Mouse, and Arabidopsis thaliana.
- Superior Recall: In human datasets, Bermuda recovered 10,171 transcripts at ≥90% completeness, outperforming Trinity (8,330) and IDBA (9,194).
- Low-Expression Performance: Bermuda's adaptive strategy proved particularly effective for lowly-expressed transcripts, consistently outperforming rivals in the lowest expression quantiles.
- Efficiency: Bermuda demonstrated high computational efficiency. For the human dataset, it required approximately 20GB of RAM, whereas Oases failed to complete the task even with 126GB available.
Conclusion
Bermuda represents a significant step forward in de novo transcriptome assembly by recognizing that the optimal k-mer size is a local, rather than global, property. By combining adaptive k-mer selection with bidirectional growth, it achieves higher contiguity and lower redundancy than existing tools. Future work will focus on improving isoform deconvolution through regularized network flow and integrating long-read data to further enhance full-length transcript reconstruction.
Summary updated