<p>It sounds like bedtools is behaving properly. The bam file is sorted by read name only if you used the <code>-n</code> option in <code>samtools sort</code>. Otherwise, if you used <code>samtools sort</code> without the name-sort option, it is 'ordered' by reference name (which can be arbitrarily ordered, as I'll explain below) and then by position (which is numerically ordered). </p>

<p>I think you are getting confused about 'ordering' the reference names. There are multiple ways to sort names; Some people might want numeric sorting (chr1, chr2, chr3...) and others might want lexicographic sorting (chr1, chr10, chr11...). Because of this, many tools allow you to specify the way you want to order the reference names. </p>

<p>There isn't necessary only one correct way to sort the reference names; what matters is that the order is the same between the files you're trying to intersect. This is exactly the purpose of <code>bedtools intersect -g</code>. </p>

<p>If you want to check the order of reference names in your bam, you can easily do so by checking the header via <code>samtools view -h input.bam</code>. It will say something like this: </p>

<pre><code>@HD     VN:1.3  SO:coordinate
@SQ     SN:chr1     LN:248956422
@SQ     SN:chr10    LN:133797422
@SQ     SN:chr11    LN:135086622
@SQ     SN:chr12    LN:133275309
</code></pre>

<p>The <code>@SQ</code> lines tell you how your bam is sorted. My suspicion is that this order is different from the Linux <code>sort</code> or <code>bedtools sort</code> default, which is why your <code>bedtools intersect</code> was failing. </p>

CC BY-SA 4.0
2019-09-25T21:04:52.350Z
It would seem that if I sort without -n, it thinks the chromosomes are out of order, and if I sort with -n option it thinks the coordinate order is wrong.  The only fix I have is forcing the order of the .bed file with the -g option.
KirkD-CO
CC BY-SA 4.0
2019-09-25T21:12:41.990Z
`samtools sort -n` does not sort by reference name (the 3rd column of a bam file). It sorts by read name (ie. the first column of a bam file).
Lynn
CC BY-SA 4.0
2019-09-25T23:33:54.050Z
Inadvertently deleted my first comment. while updating my original post.  Oops.   Here's what was in my clipboard buffer: Yes, I've done sorting with samtools sort without the -n option, giving the error above. If I sort with the -n option, I get a different error: Error: Sorted input specified, but the file sorted.bam has the following out of order If I look at the header of the .bam file when the -n option wasn't used, the first line is '@HD VN:1.0 SO:coordinate` . I interpret SO:coordinate to mean that the Sort Order is by coordinate, which is consistent with what the documentation says.
KirkD-CO
CC BY-SA 4.0
2019-09-25T20:28:06.217Z
2019-09-25T21:34:53.497Z
2019-09-25T21:34:53.497Z
Lynn
<p>As per <a href="https://bioinformatics.stackexchange.com/a/10480/240">Lynn's answer</a>, sorting is dependent on how chromosomes/contigs are named, how you want them to be sorted, etc.</p>

<p><code>samtools sort</code> or <code>sambamba sort</code> will sort as per the <a href="https://samtools.github.io/hts-specs/SAMv1.pdf" rel="nofollow noreferrer">SAM specification</a> by the order of the contigs in the header of the file. If you've aligned these sequences to a human reference genome, typically it will be <code>chr1</code>, <code>chr2</code>, ... <code>chr10</code>, <code>chr11</code>, ...</p>

<p>To sort the BED file in the same way, you can specify the sort order with the <code>bedtools sort -g</code> option and providing the explicit order.</p>

<p>Alternatively, use <code>sort</code> with the <code>-V, --version-sort</code> option, that provides a "natural sort of (version) numbers within text".</p>

<pre><code>sambamba sort -o output.bam input.bam
sort -k1,1 -V -k2,2n input.bed &gt; sorted.bed
bedtools intersect -sorted -c -a sorted.bed -b input.bam &gt; intersect_linuxsorted.out
</code></pre>

CC BY-SA 4.0
2019-09-27T17:22:02.067Z
Thanks for the response.  As I mention above, I have used the -g option that you suggest, which seems the most useful solution for my workflow.  The concern I had is that this specified ordering is not consistent with how bedtools would normally sort the .bed file and question is whether this atypical sorting would affect the intersect operation.
KirkD-CO
CC BY-SA 4.0
2019-09-30T13:39:03.297Z
As far as I'm aware, bedtools doesn't care what positional order you sort them in, just that all the files are in the same order. So `bedtools sort -g` is probably your best option to force a specific chromosomal ordering
James Hawley
CC BY-SA 4.0
2019-10-01T00:00:17.823Z
Thanks, James!  That is consistent with what I see, but not knowing what's going on under the hood makes me question things a bit.
KirkD-CO
CC BY-SA 4.0
2019-09-27T13:53:24.283Z
2019-09-27T13:53:24.283Z
James Hawley
<p>I need to do a bedtools intersect operation on a <em>very</em> large .bam file.  When I use the standard bedtools intersect operation, the process consumes all the memory on my system.</p>

<p>From the bedtools documentation page, I find the <code>-sorted</code> option to <code>bedtools intersect</code>, which sounds like it is the perfect solution to the problem, but the documentation seems incomplete.  From the documentation, I need to ensure that the .bed file is sorted and I can use either <code>bedtools sort</code> or the Linux <code>sort</code> command to accomplish this:</p>

<pre><code>bedtools sort -chrThenSizeA -i input.bed &gt; sorted.bed

sort -k1,1 -k2,2n input.bed &gt; sorted.bed
</code></pre>

<p>If I then execute the intersect operation on the .bam file, I get an error.</p>

<pre><code>bedtools intersect -sorted -c -a sorted.bed -b input.bam &gt; intersect_linuxsorted.out
ERROR: chromomsome sort ordering for file input.bam is inconsistent with other files.
</code></pre>

<p>Tracking this down I find that <code>samtools sort</code>, which was executed on the .bam file, "sorts by the leftmost coordinate, or the read name if -n is used."  It would appear there is no way to put the .bam file in order by reference name, which is what bedtools instructs.</p>

<p>For a workaround, <code>bedtools sort</code> does have the <code>-g</code> option, which allows me to specify the ordering of the .bed file.  To get this ordering, I execute:</p>

<pre><code>samtools view input.bam | cut -f3 | unique &gt; order.txt
bedtools sort -g order.txt &gt; alt_sorted.bed
</code></pre>

<p>This puts the .bed file into the same order as the .bam file, and the <code>bedtools intersect -sorted</code> command now works, but is it working correctly?  It seems that <code>bedtools intersect -sorted</code> wants the files in consistent ordering, which can be done, but is that consistent with the intersect algorithm itself?  From the documentation's instructions to sort by the first 2 fields, chromosome name and left-most coordinate, it seems inconsistent to order it as the .bam file is ordered, by read name and not reference name.  </p>

<p>I'm not sure how to check this assumption.</p>

<p>EDIT:  Some extra details regarding sorting of the .bam file.</p>

<p>If the .bam file is sorted with <code>samtools sort input.bam &gt; sorted.bam</code> I get the error, 'ERROR: chromomsome sort ordering for file input.bam is inconsistent with other files`</p>

<p>If the .bam file is sorted with <code>samtools sort -n input.bam &gt; sorted.bam</code> I get this error, <code>Error: Sorted input specified, but the file sorted.bam has the following out of order</code></p>

<p>It would seem that if I sort without -n, it thinks the chromosomes are out of order, and if I sort with -n option it thinks the coordinate order is wrong. The only fix I have is forcing the order of the .bed file with the -g option, but again, I have no idea if that is consistent with the underlying algorithm's assumptions for the -sorted option.</p>

CC BY-SA 4.0
2019-09-25T20:36:58.660Z
As a workaround, you could just split your bed file into one file per chromosome, run the intersect for each of those, and then merge the resulting bam files. Clearly not optimal, but if all else fails, it might give you a way out.
terdon
CC BY-SA 4.0
2019-09-25T20:52:25.857Z
Thanks for the suggestion.  Unfortunately, that's not a workable option given the workflow that I currently have.
KirkD-CO
<samtools><bedtools>
bedtools intersect on very large .bam file - -sorted confusion
# bedtools intersect on very large .bam file - -sorted confusion

(Asked by: username_0 on 2019-09-25)

I need to do a bedtools intersect operation on a very large .bam file.  When I use the standard bedtools intersect operation, the process consumes all the memory on my system.
From the bedtools documentation page, I find the -sorted option to bedtools intersect, which sounds like it is the perfect solution to the problem, but the documentation seems incomplete.  From the documentation, I need to ensure that the .bed file is sorted and I can use either bedtools sort or the Linux sort command to accomplish this:
bedtools sort -chrThenSizeA -i input.bed > sorted.bed

sort -k1,1 -k2,2n input.bed > sorted.bed

If I then execute the intersect operation on the .bam file, I get an error.
bedtools intersect -sorted -c -a sorted.bed -b input.bam > intersect_linuxsorted.out
ERROR: chromomsome sort ordering for file input.bam is inconsistent with other files.

Tracking this down I find that samtools sort, which was executed on the .bam file, "sorts by the leftmost coordinate, or the read name if -n is used."  It would appear there is no way to put the .bam file in order by reference name, which is what bedtools instructs.
For a workaround, bedtools sort does have the -g option, which allows me to specify the ordering of the .bed file.  To get this ordering, I execute:
samtools view input.bam | cut -f3 | unique > order.txt
bedtools sort -g order.txt > alt_sorted.bed

This puts the .bed file into the same order as the .bam file, and the bedtools intersect -sorted command now works, but is it working correctly?  It seems that bedtools intersect -sorted wants the files in consistent ordering, which can be done, but is that consistent with the intersect algorithm itself?  From the documentation's instructions to sort by the first 2 fields, chromosome name and left-most coordinate, it seems inconsistent to order it as the .bam file is ordered, by read name and not reference name.  
I'm not sure how to check this assumption.
EDIT:  Some extra details regarding sorting of the .bam file.
If the .bam file is sorted with samtools sort input.bam > sorted.bam I get the error, 'ERROR: chromomsome sort ordering for file input.bam is inconsistent with other files`
If the .bam file is sorted with samtools sort -n input.bam > sorted.bam I get this error, Error: Sorted input specified, but the file sorted.bam has the following out of order
It would seem that if I sort without -n, it thinks the chromosomes are out of order, and if I sort with -n option it thinks the coordinate order is wrong. The only fix I have is forcing the order of the .bed file with the -g option, but again, I have no idea if that is consistent with the underlying algorithm's assumptions for the -sorted option.

**Tags:** samtools, bedtools
> **Comments:**
> **username_1**: As a workaround, you could just split your bed file into one file per chromosome, run the intersect for each of those, and then merge the resulting bam files. Clearly not optimal, but if all else fails, it might give you a way out.  
> **username_0**: Thanks for the suggestion.  Unfortunately, that's not a workable option given the workflow that I currently have.  

---

## 2 answers

### Answer by username_2 on 2019-09-25. Score: 4

It sounds like bedtools is behaving properly. The bam file is sorted by read name only if you used the -n option in samtools sort. Otherwise, if you used samtools sort without the name-sort option, it is 'ordered' by reference name (which can be arbitrarily ordered, as I'll explain below) and then by position (which is numerically ordered). 
I think you are getting confused about 'ordering' the reference names. There are multiple ways to sort names; Some people might want numeric sorting (chr1, chr2, chr3...) and others might want lexicographic sorting (chr1, chr10, chr11...). Because of this, many tools allow you to specify the way you want to order the reference names. 
There isn't necessary only one correct way to sort the reference names; what matters is that the order is the same between the files you're trying to intersect. This is exactly the purpose of bedtools intersect -g. 
If you want to check the order of reference names in your bam, you can easily do so by checking the header via samtools view -h input.bam. It will say something like this: 
@HD     VN:1.3  SO:coordinate
@SQ     SN:chr1     LN:248956422
@SQ     SN:chr10    LN:133797422
@SQ     SN:chr11    LN:135086622
@SQ     SN:chr12    LN:133275309

The @SQ lines tell you how your bam is sorted. My suspicion is that this order is different from the Linux sort or bedtools sort default, which is why your bedtools intersect was failing.

> **Comments:**
> **username_0**: It would seem that if I sort without -n, it thinks the chromosomes are out of order, and if I sort with -n option it thinks the coordinate order is wrong.  The only fix I have is forcing the order of the .bed file with the -g option.  
> **username_2**: `samtools sort -n` does not sort by reference name (the 3rd column of a bam file). It sorts by read name (ie. the first column of a bam file).  
> **username_0**: Inadvertently deleted my first comment. while updating my original post.  Oops.   Here's what was in my clipboard buffer: Yes, I've done sorting with samtools sort without the -n option, giving the error above. If I sort with the -n option, I get a different error: Error: Sorted input specified, but the file sorted.bam has the following out of order If I look at the header of the .bam file when the -n option wasn't used, the first line is '@HD VN:1.0 SO:coordinate` . I interpret SO:coordinate to mean that the Sort Order is by coordinate, which is consistent with what the documentation says.  

---

### Answer by username_3 on 2019-09-27. Score: 1

As per Lynn's answer, sorting is dependent on how chromosomes/contigs are named, how you want them to be sorted, etc.
samtools sort or sambamba sort will sort as per the SAM specification by the order of the contigs in the header of the file. If you've aligned these sequences to a human reference genome, typically it will be chr1, chr2, ... chr10, chr11, ...
To sort the BED file in the same way, you can specify the sort order with the bedtools sort -g option and providing the explicit order.
Alternatively, use sort with the -V, --version-sort option, that provides a "natural sort of (version) numbers within text".
sambamba sort -o output.bam input.bam
sort -k1,1 -V -k2,2n input.bed > sorted.bed
bedtools intersect -sorted -c -a sorted.bed -b input.bam > intersect_linuxsorted.out

> **Comments:**
> **username_0**: Thanks for the response.  As I mention above, I have used the -g option that you suggest, which seems the most useful solution for my workflow.  The concern I had is that this specified ordering is not consistent with how bedtools would normally sort the .bed file and question is whether this atypical sorting would affect the intersect operation.  
> **username_3**: As far as I'm aware, bedtools doesn't care what positional order you sort them in, just that all the files are in the same order. So `bedtools sort -g` is probably your best option to force a specific chromosomal ordering  
> **username_0**: Thanks, James!  That is consistent with what I see, but not knowing what's going on under the hood makes me question things a bit.  

---

