Algorithms for efficiently collapsing reads with Unique Molecular Identifiers
Abstract
Background
Unique Molecular Identifiers (UMI) are used in many experiments to find and remove PCR duplicates. Although there are many tools for solving the problem of deduplicating reads based on their finding reads with the same alignment coordinates and UMIs, many tools either cannot handle substitution errors, or require expensive pairwise UMI comparisons that do not efficiently scale to larger datasets.
Results
We formulate the problem of deduplicating UMIs in a manner that enables optimizations to be made, and more efficient data structures to be used. We implement our data structures and optimizations in a tool called UMICollapse, which is able to deduplicate over one million unique UMIs of length 9 at a single alignment position in around 26 seconds.
Conclusions
We present a new formulation of the UMI deduplication problem, and show that it can be solved faster, with more sophisticated data structures.
Related articles
Related articles are currently not available for this article.