Sourmash, k-mer sketches and open-source software with Titus Brown
Andrew Page and Lee Katz continue their conversation with Titus Brown about k-mers, Sourmash and open-source bioinformatics. Brown explains how fractional sketches support comparisons between genomes and metagenomes, why reference-based searches can tolerate sequencing errors, and why he favours reusable libraries over single-purpose tools. The discussion also explores how open collaboration shapes both the software and the people working on it.
In this episode
From khmer to compact sketches
Brown’s interest in Sourmash grew out of extensive work with k-mers in khmer and digital normalisation. K-mers offered a computer-friendly way to examine sequencing data, but working with them in large genomes and metagenomes could become computationally heavy. MinHash was attractive because a representative subsample could stand in for a much larger collection, allowing fast comparisons without carrying every k-mer through the analysis.
Sourmash began as Brown’s Python reimplementation of MASH: a way to experiment with a relatively simple algorithm and understand its behaviour. He admits that the first year’s implementation was broken, but it still helped him explore the approach before someone corrected it. He describes Jaccard similarity as a numerical way to compare sets, useful for clustering and large-scale searches. The difficulty that drove further development was comparing sets whose sizes differed substantially, particularly a bacterial genome and a metagenome.
Why sampling a fraction changes the comparison
Brown contrasts retaining a fixed number of k-mers with retaining a fixed fraction. In his explanation, MASH works well when comparing bacterial genomes of roughly similar size. Comparing a genome with a much larger metagenome is harder: fixed-size sketches may have very little overlap, making them unsuitable for the containment question he wanted to answer.
The alternative he rediscovered was ModHash. Instead of keeping 1,000 k-mers from every dataset, the method could sample one in every 1,000. Larger datasets then produce larger sketches, while smaller datasets produce smaller ones. This supports questions such as how many of a bacterial genome’s k-mers occur in a metagenome.
Sourmash uses a bottom-sketch variant called FracMinHash. Brown describes hashing the 4^k possible k-mers and retaining those in the bottom fraction of hash space—for example, the bottom one-thousandth. Whenever one of those k-mers appears in a dataset, it is recorded.
Sequencing errors are not the same as low abundance
Asked about sequencing noise, Brown argues for methods that remain useful in its presence rather than requiring every error to be removed beforehand. Low abundance alone is a poor filter for metagenomes: genuine organisms can be rare, and soil metagenomes contain substantial low-abundance signal. Removing those k-mers can discard real biology alongside errors.
Earlier khmer work used a streaming approach to remove low-abundance k-mers from otherwise high-abundance reads. Brown says it worked reasonably well but, because it still looked at all of the data, was too slow for real practical use. He stresses the cost of making repeated passes through metagenomic datasets.
His working compromise in Sourmash is reference-based analysis. Erroneous k-mers tend not to match references, although he explicitly presents this as an imperfect generalisation. Abundance-weighted reporting also helps assess the unmatched fraction; his example of 5% unknown abundance-weighted k-mers is illustrative, not a reported dataset result. The trade-off is that missing references remain missing discoveries. After about five years, his group concluded that the reference-based metagenomic analyses they were doing did not require abundance filtering or error trimming.
Libraries for research questions that keep changing
Brown says his group worked out the FracMinHash approach around 2017 and then implemented it robustly in Sourmash. Development also included checks that sketches used compatible k-mer sizes, efficient searches across large collections, and Python APIs for working with k-mer sets. These supporting pieces matter to him because he wants a library for exploring new questions, rather than a tool restricted to one task.
He favours rapid iteration, while acknowledging the cost: software and research can become messy and difficult to explain while the computational approach is still being worked out. Digital normalisation and Sourmash are his examples of useful approaches emerging from that style of exploration. He also describes concentrating on problems he needs to solve, leaving other capabilities to tools that already handle them well. Rather than beginning with extensive reading, he often tries to understand the underlying technical problem and recognise approaches he can borrow.
Collaboration through interesting problems and open code
Brown describes recruiting computational collaborators through “nerd sniping”: putting an interesting problem in front of someone who may want to pursue it. One major Sourmash collaborator began contributing pull requests after seeing useful work in a GitHub repository, then added data structures and algorithms and became a co-equal contributor. Brown also recalls meeting that collaborator through the Python community before recruiting him from Brazil to graduate school.
Lee Katz offers the view from outside the project. He remembers Brown asking implementation questions on the MASH repository, including which random seed it used, while developing Sourmash. Katz was interested in using the approach for trees and clustering and enjoyed watching the work progress.
Brown traces his open-source habits to early access to Unix and programming before his scientific career. He mentions screen, a chat program called Ring and work on the game Dominion. His principle is to make research software available for others to use, rather than withholding it while working out how to secure credit.
Highlights
- 00:01:07 — Earlier k-mer work in khmer and the appeal of lightweight MinHash sketches
- 00:07:01 — Designing analyses that remain useful in the presence of sequencing noise
- 00:07:46 — Why low-abundance filtering can remove real metagenomic signal
- 00:09:21 — The strengths and limits of Sourmash’s reference-based applications
- 00:10:54 — Working out FracMinHash around 2017 and building reusable Sourmash APIs
- 00:13:13 — Recruiting computational collaborators through nerd sniping
- 00:14:36 — How a Python programmer from Brazil joined Brown’s lab
- 00:16:35 — Lee Katz recalls watching Sourmash develop through the MASH repository
- 00:17:20 — The early Unix and open-source experiences Brown brought to bioinformatics
- 00:18:29 — High-school programming projects and the principle of sharing research software
In their own words
So by and large, if you don’t have it in your database, we don’t find it with sourmash.
— Titus Brown, 00:09:21
We’re supposed to be letting others make use of what we do.
— Titus Brown, 00:18:29
Who is talking
- Titus Brown (guest)
- Andrew Page (host)
- Lee Katz (host)
Tools and resources mentioned
khmer, Sourmash, MASH, MinHash, ModHash, FracMinHash, bottom sketch, Jaccard similarity, digital normalisation, GitHub, screen, tmux, Ring, Dominion.
Questions this episode answers
How does Sourmash compare a bacterial genome with a much larger metagenome?
Brown describes Sourmash’s FracMinHash approach as retaining a consistent fraction of hash space rather than a fixed number of k-mers. This produces sketches that scale with dataset size and supports estimating how much of a genome’s k-mer content occurs in a metagenome.
Should low-abundance k-mers be removed before metagenomic analysis?
Brown warns that low-abundance k-mers can represent genuine biological signal, especially in datasets such as soil metagenomes. For the reference-based Sourmash analyses his group was doing, they concluded that abundance filtering and error trimming were unnecessary because erroneous k-mers generally did not match references.
Can Sourmash identify organisms that are absent from its reference database?
Brown says that Sourmash’s most popular applications are reference-based: if something is absent from the database, those searches do not find it. He presents this as both a strength, because errors tend not to match, and a limitation on discovery.
Why does Titus Brown prefer reusable libraries to single-purpose tools?
He wants to investigate different computational questions as they arise, using reusable components and Python APIs rather than building a separate tool for each one. He values rapid iteration but acknowledges that this can leave software and research in a messy, difficult-to-explain state.
This page was written from a machine transcript of the episode and checked against it. Listen to the episode for the whole conversation.
Show notes
In this episode, Andrew Page and Lee Katz continue their conversation with Titus Brown, diving deeper into his work on k-mers, Sourmash, and open source software development:
Topics discussed:
K-mers for analyzing sequencing data, and how Sourmash builds on MinHash How Sourmash handles k-mers for metagenomic comparisons vs. MASH The modhash and bottom sketch approaches used in Sourmash Dealing with sequencing errors and noise in k-mer data Sourmash as a reference-based method, and applications for metagenomics Titus’ focus on building reusable libraries and APIs vs one-off tools Recruiting collaborators through “nerd sniping” with interesting problems The open source philosophy that motivates Titus’ software work Overall, the conversation provides insight into Titus’ approach to bioinformatics software through iterating quickly, focusing on usability, and building open source tools.
Papers: Spacegraphcats - https://genomebiology.biomedcentral.com/articles/10.1186/s13059-020-02066-4 Sourmash - https://www.biorxiv.org/content/10.1101/2022.01.11.475838v2 IBD exploration - <https://dib- lab.github.io/2021-paper-ibd/>