Source-linked AI summary
Btrim: A fast, lightweight adapter and quality trimming program for next-generation sequencing technologies
Yong Kong
TL;DR
Next-generation sequencing generates huge sequence volumes containing adapters and low-quality regions, while assigning reads back to samples requires reliable barcode identification. Btrim presents a fast, lightweight stand-alone approach for trimming and barcode identification, with a 57-second runtime and memory usage below 1M.
Problem
Huge next-generation sequencing volumes require more efficient software, including reliable barcode identification to assign reads back to their original samples.
Method
Btrim is a fast, lightweight program for adapter and quality trimming based on a modified Myers’s algorithm.
Results
57 seconds and less than 1M memory footprint are reported for Btrim, with reads processed sequentially.
Takeaways & Limitations
Btrim is presented as a versatile stand-alone program for flexible downstream sequence analysis.
Abstract
from arXiv · showhide
Btrim is a fast and lightweight software to trim adapters and low quality regions in reads from ultra high-throughput next-generation sequencing machines. It also can reliably identify barcodes and assign the reads to the original samples. Based on a modified Myers's bit-vector dynamic programming algorithm, Btrim can handle indels in adapters and barcodes. It removes low quality regions and trims off adapters at both or either end of the reads. A typical trimming of 30M reads with two sets of adapter pairs can be done in about a minute with a small memory footprint. Btrim is a versatile stand-alone tool that can be used as the first step in virtually all next-generation sequence analysis pipelines. The program is available at \url{http://graphics.med.yale.edu/trim/}.
1. Introduction
Next-generation sequencing produces large read volumes containing adapters, barcodes, and declining-quality regions that can disrupt mapping and downstream analyses. Btrim addresses these preprocessing needs as a fast, lightweight, stand-alone trimming and barcode-identification program.
- Motivation: Adapters and other exogenous sequences can prevent mapping or increase false positives in downstream variant analysis.These sequences are not biological and may be treated as matching errors or interfere with downstream analysis if retained.
- Motivation: Read quality commonly declines toward read ends, so sequencing errors can impair mapping even when earlier bases remain high quality.The issue becomes more important as sequence lengths increase.
- Motivation: Barcode identification is needed to assign pooled sequencing reads back to their original samples despite experimental and sequencing errors.Barcodes are distinct sequence tags ligated to DNA from individual samples.
- Problem: The large volume of next-generation sequencing data requires more efficient software than approaches developed for small numbers of sequences.A versatile stand-alone program also supports flexible downstream analysis with different mapping or assembly packages.
- Contribution: The processed sequences can be supplied to different mapping or assembly programs, while alternative trimming parameters can be evaluated using downstream analysis.The program is intended as a flexible stand-alone preprocessing step.
- Contribution: Btrim is presented as a fast, lightweight program for adapter and quality trimming, with adapter searches based on a modified Myers bit-vector dynamic programming algorithm.Quality trimming uses a moving window that trims where the average quality score falls below a threshold.
2. Bit-vector dynamic programming algorithm for adapter trimming and barcode identification
Btrim adapts bit-vector dynamic programming to locate adapters and barcodes efficiently while supporting indel-tolerant matching and quality-based fallback trimming. Its workflow handles adapter-pair searches, quality trimming, ambiguous bases, and optional trimming records.
- Algorithm: Myers’s bit-vector algorithm finds query occurrences with up to k errors and gives Btrim time complexity O(qn) for q adapter or barcode queries.The search preprocesses queries, then scans target sequences sequentially.
- Algorithm: Btrim modifies Myers’s algorithm to recover query starting positions needed to define precise adapter boundaries without conventional traceback.The modified search proceeds backward along the target sequence for 3′-adapter searches.
- Trimming modes: Btrim supports configurable error thresholds, adapter-only or fallback quality-trimming modes, and quality-score-only trimming.Default k values are 3 for 5′ adapters and 4 for 3′ adapters, but users can change them.
- Sequence matching: The algorithm handles ambiguous and wildcard letters, supporting adapters with degenerate bases and optional case-sensitive searching.Ambiguous bases can use bracket notation, wildcards use '.', and IUPAC codes are supported.
- Output: Btrim can write trimmed fragments, quality scores, trimming status, detected adapters or barcodes, errors, and locations to a separate file.The output can support downstream analyses such as barcode assignment.
- Performance: 57 seconds processes 30M 75bp Illumina reads with two sets of adapter pairs, while memory usage remains below 1M.The timing was measured on a 3.16GHz Intel Xeon processor.