Look at allowing mis-matches in the k-mers

No mismatches, taking about 10M of RAM only,

$ time samtools view 7261_6.bam | ./blooming_reads.py -c all_mito.fas -f sam -k 20 -m 0 > /dev/null
Hashing circular references in all_mito.fas
Set and bloom filter of 20-mers created (79972 k-mers considered, 48864 unique)
Using Bloom filter with capacity 48864 and error rate 0.01
Building filters took 0.1s
Processed 100000 reads, kept 2162 (2.2%), taken 2.9s (of which 2.2s in filter)
Processed 200000 reads, kept 4406 (2.2%), taken 5.9s (of which 4.4s in filter)
Processed 300000 reads, kept 6630 (2.2%), taken 8.8s (of which 6.6s in filter)
Processed 400000 reads, kept 8796 (2.2%), taken 11.7s (of which 8.8s in filter)
Processed 500000 reads, kept 10982 (2.2%), taken 14.7s (of which 11.0s in filter)
Processed 600000 reads, kept 13140 (2.2%), taken 17.6s (of which 13.3s in filter)
Processed 700000 reads, kept 15322 (2.2%), taken 20.5s (of which 15.5s in filter)
Processed 800000 reads, kept 17474 (2.2%), taken 23.5s (of which 17.7s in filter)
Processed 900000 reads, kept 19688 (2.2%), taken 26.4s (of which 19.9s in filter)
Processed 1000000 reads, kept 21926 (2.2%), taken 29.4s (of which 22.1s in filter)
Processed 1100000 reads, kept 24086 (2.2%), taken 32.3s (of which 24.3s in filter)
...

With one mis-match per k-mer, seems we accept about twice the number of reads:

$ time samtools view 7261_6.bam | ./blooming_reads.py -c all_mito.fas -f sam -k 20 -m 1 > /dev/null
Hashing circular references in all_mito.fas
Have 48864 unique k-mers before consider 1 mis-matches
Adding 1 mis-matches per k-mer, have 2933960 unique k-mers
Set and bloom filter of 20-mers created (79972 k-mers considered, 2933960 unique)
Using Bloom filter with capacity 2933960 and error rate 0.01
Building filters took 7.4s
Processed 100000 reads, kept 5754 (5.8%), taken 3.6s (of which 2.8s in filter)
Processed 200000 reads, kept 11340 (5.7%), taken 7.2s (of which 5.7s in filter)
Processed 300000 reads, kept 16924 (5.6%), taken 10.7s (of which 8.5s in filter)
Processed 400000 reads, kept 22500 (5.6%), taken 14.3s (of which 11.3s in filter)
Processed 500000 reads, kept 28144 (5.6%), taken 17.9s (of which 14.1s in filter)
Processed 600000 reads, kept 33772 (5.6%), taken 21.4s (of which 17.0s in filter)
Processed 700000 reads, kept 39316 (5.6%), taken 25.0s (of which 19.8s in filter)
Processed 800000 reads, kept 44642 (5.6%), taken 28.6s (of which 22.6s in filter)
Processed 900000 reads, kept 50010 (5.6%), taken 32.1s (of which 25.4s in filter)
Processed 1000000 reads, kept 55622 (5.6%), taken 35.7s (of which 28.2s in filter)
Processed 1100000 reads, kept 61046 (5.5%), taken 39.2s (of which 31.0s in filter)
...
Experiment with checking for single base inserts

$ time samtools view 7261_6.bam | ./blooming_reads.py -c all_mito.fas -f sam -k 35 -m 1 > /dev/null
Hashing circular references in all_mito.fas
Have 54128 unique k-mers before consider mis-matches/inserts
Adding 1 mis-matches per k-mer, have 5706047 unique k-mers
Adding inserts brings this to 11061445 unique k-mers
Set and bloom filter of 35-mers created (79972 k-mers considered, 11061445 unique)
Using Bloom filter with capacity 11061445 and error rate 0.01
Building filters took 29.7s
Processed 100000 reads, kept 1272 (1.3%), taken 3.7s (of which 2.9s in filter)
Processed 200000 reads, kept 2562 (1.3%), taken 7.3s (of which 5.8s in filter)
Processed 300000 reads, kept 3806 (1.3%), taken 11.0s (of which 8.7s in filter)
Processed 400000 reads, kept 5052 (1.3%), taken 14.7s (of which 11.5s in filter)
Processed 500000 reads, kept 6272 (1.3%), taken 18.3s (of which 14.4s in filter)
Processed 600000 reads, kept 7482 (1.2%), taken 22.0s (of which 17.2s in filter)
Processed 700000 reads, kept 8762 (1.3%), taken 25.6s (of which 20.1s in filter)
Processed 800000 reads, kept 9996 (1.2%), taken 29.3s (of which 23.0s in filter)
...

(which took about 1GB or RAM), or:

$ time samtools view 7261_6.bam | ./blooming_reads.py -c all_mito.fas -f sam -k 20 -m 1 > /dev/null
Hashing circular references in all_mito.fas
Have 48864 unique k-mers before consider mis-matches/inserts
Adding 1 mis-matches per k-mer, have 2933960 unique k-mers
Adding inserts brings this to 5543205 unique k-mers
Set and bloom filter of 20-mers created (79972 k-mers considered, 5543205 unique)
Using Bloom filter with capacity 5543205 and error rate 0.01
Building filters took 13.5s
Processed 100000 reads, kept 5754 (5.8%), taken 3.9s (of which 3.1s in filter)
Processed 200000 reads, kept 11340 (5.7%), taken 7.7s (of which 6.2s in filter)
Processed 300000 reads, kept 16924 (5.6%), taken 11.6s (of which 9.3s in filter)
Processed 400000 reads, kept 22500 (5.6%), taken 15.4s (of which 12.4s in filter)
Processed 500000 reads, kept 28144 (5.6%), taken 19.3s (of which 15.5s in filter)
Processed 600000 reads, kept 33772 (5.6%), taken 23.1s (of which 18.7s in filter)
Processed 700000 reads, kept 39316 (5.6%), taken 27.0s (of which 21.8s in filter)
...
Check for ambiguous references...
Disambiguate references sequences (e.g. expand N into A, C, G or T)

Any k-mer in the reference with an N becomes 4 new k-mers using A, C, G and T
for that base. Likewise for the other IUPAC ambiguity codes.

$ time samtools view 7261_6.bam | ./blooming_reads.py -c all_mito.fas -f sam -k 20 -m 1 > /dev/null
Hashing circular references in all_mito.fas
Have 63695 unique k-mers before consider mis-matches/inserts
Adding 1 mis-matches per k-mer, have 3558411 unique k-mers
Adding inserts brings this to 6657783 unique k-mers
Set and bloom filter of 20-mers created (95955 k-mers considered, 6657783 unique)
Using Bloom filter with capacity 6657783 and error rate 0.01
Building filters took 18.1s
Processed 100000 reads, kept 7526 (7.5%), taken 3.9s (of which 3.1s in filter)
Processed 200000 reads, kept 14756 (7.4%), taken 7.7s (of which 6.2s in filter)
Processed 300000 reads, kept 22024 (7.3%), taken 11.6s (of which 9.3s in filter)
Processed 400000 reads, kept 29232 (7.3%), taken 15.4s (of which 12.4s in filter)
Processed 500000 reads, kept 36520 (7.3%), taken 19.3s (of which 15.5s in filter)
...

$ time samtools view 7261_6.bam | ./blooming_reads.py -c all_mito.fas -f sam -k 20 -m 0 > /dev/null
Hashing circular references in all_mito.fas
Set and bloom filter of 20-mers created (95955 k-mers considered, 63695 unique)
Using Bloom filter with capacity 63695 and error rate 0.01
Building filters took 0.6s
Processed 100000 reads, kept 2556 (2.6%), taken 2.9s (of which 2.2s in filter)
Processed 200000 reads, kept 5096 (2.5%), taken 5.8s (of which 4.4s in filter)
Processed 300000 reads, kept 7600 (2.5%), taken 8.7s (of which 6.5s in filter)
Processed 400000 reads, kept 10088 (2.5%), taken 11.6s (of which 8.7s in filter)
Processed 500000 reads, kept 12604 (2.5%), taken 14.6s (of which 10.9s in filter)
Processed 600000 reads, kept 15086 (2.5%), taken 17.5s (of which 13.1s in filter)
...

Recall prior to looking for ambiguity codes only considered 48746 unique 20-mers.