A faster read sorter

[brofallon]

Hello,
I recently developed a fast stream-based .SAM sorter, streamsorter. It reads .SAM output from a stream (for instance, produced by bwa or another aligner), sorts the reads as they come in, and emits everything to standard out. Because this happens during alignment, and sorting is much faster than aligning, sorting takes essentially no extra time.

Here's the basic usage for use with bwa:

(long bwa command to create alignment) | sorter > sorted.sam

Or if you prefer bam output:

(long bwa command to create alignment) | sorter | samtools view -Sb - > sorted.bam

For big alignments this can easily shave a substantial amount of time from the pipeline. Enjoy! Let me know if you find a bug or have other feedback.

[maubp]

How is this better than doing this via samtools? i.e. aligner -> {SAM} -> samtools view -> {uncompressed BAM} -> samtools sort -> {sorted BAM}

$ alignment arg1 arg2 ... | samtools -S -u - | samtools sort - prefix

[brofallon]

Huh... that -u option on samtools view does seem to speed things up a bit. Stream sorter is still a bit faster for two reasons. First, it doesn't depend on piping anything though samtools view to make an uncompressed bam that samtools sort can read. Second, samtools sort doesn't create bams very quickly. Streamsorter allows plugging in faster bamifier:

Time to align, sort, and bamify ~500MB fastq;
BWA mem + samtools : 643 seconds
BWA mem + sorter : 594 seconds
BWA mem + sorter + samtools-mt to create bam: 495 seconds

Where samtools-mt is multithreaded samtools with 4 threads.
OK, not a huge speedup. But we look for everything we can get around here....

[maubp]

Try some larger files - the speedup may be more visible then.

I'd have to look at the code, but in principle 'samtools sort' could be extended to accept SAM as an input option.

[oiiio]

just wanted to say that novosort (novocraft.com) is probably the fastest read sorting I have seen.

In second place is the OpenGE's mergesort function which is open source (git://github.com/adaptivegenome/openge.git)