Source-linked AI summary
biobambam: tools for read pair collation based algorithms on BAM files
German Tischler, Steven Leonard
TL;DR
The paper addresses efficient collation of BAM alignments by read name. It presents an API and associated tools, reporting fast processing for most nearby read pairs while limiting excessive memory use, with possible memory increases for distant pairs.
Problem
Efficiently collating BAM alignments by read name is the paper's central problem.
Method
The paper presents an API for extracting BAM alignments by name and tools including bamtofastq and bammarkduplicates.
Results
The approach quickly processes most reads with both ends close together in the BAM file while avoiding excessive main-memory use for pairs that are not close together.
Takeaways & Limitations
The presented algorithms and data structures support name-collated BAM file input and associated read-processing tools.
Takeaways & Limitations
Some read ends can remain in the hash table for an extended time, causing a drastic increase in required memory.
Abstract
from arXiv · showhide
Sequence alignment data is often ordered by coordinate (id of the reference sequence plus position on the sequence where the fragment was mapped) when stored in BAM files, as this simplifies the extraction of variants between the mapped data and the reference or of variants within the mapped data. In this order paired reads are usually separated in the file, which complicates some other applications like duplicate marking or conversion to the FastQ format which require to access the full information of the pairs. In this paper we introduce biobambam, an API for efficient BAM file reading supporting the efficient collation of alignments by read name without performing a complete resorting of the input file and some tools based on this API performing tasks like marking duplicate reads and conversion to the FastQ format. In comparison with previous approaches to problems involving the collation of alignments by read name like the BAM to FastQ or duplication marking utilities in the Picard suite the approach of biobambam can often perform an equivalent task more efficiently in terms of the required main memory and run-time.
Implementation
biobambam collates BAM alignments by read name using bounded in-memory structures, overflow handling, and sorted temporary files rather than fully resorting the input. Its API and front-end tools support read-pair processing while limiting memory use for distant or unusually distributed pairs.
- Package and API: The package provides an API for collating BAM alignments by read name and front-end tools including bamtofastq and bammarkduplicates.The implementation is part of libmaus, while the front-end programs are in the biobambam project.
- Memory-aware processing: The design quickly processes pairs whose ends are close in coordinate order while avoiding excessive main memory for pairs that are not close together.This behavior is motivated by the observation that paired alignments are often separated but commonly remain near each other in coordinate-sorted BAM files.
- Scope and constraints: High-depth regions, split reads, and improperly mapped pairs can produce atypical collation distances or sharply increase memory requirements.The reported median separation is 107 alignments, while improperly mapped pairs make the weighted average uninformative; unusually high coverage can increase hash-table memory substantially.
- Collation algorithm: Most alignments are handled in a fixed-size hash table H, while collisions are moved to a fixed-size overflow list L for later name-based sorting.When L fills, alignments are sorted by read name; unpaired records are written to temporary files.
- Collation algorithm: Sorted temporary files are merged into a read-name-sorted stream, making paired alignments easy to detect and output.The process extracts pairs during intermediate sorting when possible and again after merging the temporary files.
- Data structures: The hash table uses a character-array ring buffer R, integer pointer array P, and B-tree B, while L is stored as a byte array.These structures reduce the overhead of allocating and freeing a small memory block for every alignment.
Results and Discussion
The paper documents biobambam’s read-name collation API and associated BAM-to-FastQ and duplicate-marking tools, then compares their resource use with Picard. Across tested datasets, the tools generally provide similar or lower runtimes while using substantially less memory in challenging cases.
- Approach: biobambam provides a C++ API for read-name collation in BAM files, supporting the bamtofastq and bammarkduplicates tools.The API is used to extract paired alignments without a complete resorting workflow.
- Approach: The collation API extracts alignment pairs while allowing alignments to overflow to a temporary disk file, limiting dependence on main memory.The collator returns paired alignment pointers and can represent single or orphan reads with a null pointer.
- FastQ conversion: 3.87× faster: bamtofastq completed one comparison in 305s versus 1182s for Picard’s SamToFastq component, with both using about 256MB of heap.Neither program gained significantly from additional main memory in this comparison.
- Discussion: The tools’ memory behavior reflects their design: Picard retains read ends in a Java HashMap, whereas biobambam uses secondary memory and maintains predictable memory usage.The paper attributes Picard’s low performance near its memory limit to frequent object allocation and garbage collection.
- Duplicate marking: bammarkduplicates was faster by 1.16× on the low-depth HG00096 dataset, while both programs handled it with 256MB of heap.On ERP001231, runtime was about the same, but bammarkduplicates used 281MB and Picard was unable to handle the file with 512MB.
Conclusions
The paper presents efficient algorithms and data structures for name-collated BAM input, implemented in libmaus and used by two biobambam tools. These tools are often faster than Picard counterparts and use significantly less main memory.
- The paper presents efficient algorithms and data structures for name-collated BAM file input.
- The algorithms are implemented in libmaus, an open-source C++ programming library.
- The biobambam package provides bamtofastq and bammarkduplicates based on the API.
- The tools are often faster than their Picard counterparts and use significantly less main memory.
Authors contributions
GT wrote the code, ran tests and benchmarks, and wrote the paper, while SL contributed to testing and provided compatibility patches for bammarkduplicates.
- GT wrote the code, ran the tests and benchmarks, and wrote the paper.
- SL contributed to testing and provided patches improving bammarkduplicates compatibility with Picard’s MarkDuplicates.
Availability and requirements
biobambam/libmaus is an open-source C++ project available for Linux and MacOS X, with no restrictions on non-academic use.
- The project is named biobambam/libmaus.
- The software supports Linux and MacOS X.
- The programming language is C++.
- There are no restrictions on use by non-academics.