how to quick sort a 20G bed file?

We are often suggested to sort the input bed file by "sort -k1,1 -k2,2n" in order to invokes a memory-efficient algorithm designed for large files, for example, bedtools intersect ( http://bedtools.readthedocs.org/en/latest/content/tools/intersect.html)

But this is slow for a large file up to 20G in size.

Here are some quicker solutions for that

Solution #1:

inputbed=$1
awk -v inputbed=$inputbed '{print $0 >> inputbed"."$1}' 

#or, use "split -l 100000 $inputbed $inputbed." to split large file into small files 

for i in $inputbed.*; do sort -k2,2n $i > $i.s & done
# when it's done
sort -m -k1,1 -k2,2n $inputbed.*s > $inputbed.sorted
The trick is to split large file into small ones (in this case, one per chromosome), then sort individual one in a parallel way. Finally we merge them by "sort -m" (Note: sort-merge is not just to concatenate files, but rather sort of sorting-and-merging)

Solution #2: 

A parallel solution is to use sort from coreultils: sort --parallel=N. See my post here: http://www.biostars.org/p/66927/
LC_ALL=C sort --parallel=24 --buffer-size=2G -k1,1 -k2,2n allmap.bed > allmap.sorted.bed

Solution #3:

Use the sort-bed tool from BEDOPSsort-bed --max-mem 5G input.bed > sorted.bed

quick sort in bash line

There are varieties of sorting algorithms (see wiki for details: http://en.wikipedia.org/wiki/Sorting_algorithm). The time complexity for the quick ones are like nlog(n).

In unix, we usually use the 'sort' command to sort input. I cannot find direct info for the computational complexity of unix sort command, but definitely it shows quick slow esp. when the dataset is large.

Here are several feasible solutions for quick sorting I googled:

1. "split & merge" http://arnab.org/blog/quick-and-easy-multicore-sort

split -l5000000 data.tsv '_tmp';
ls -1 _tmp* | while read FILE; do sort $FILE -o $FILE & done;
Followed by:
sort -m _tmp* -o data.tsv.sorted

arnab suggested to split the large file into small pieces and sort them individually, then use 'sort -m' to merge them. I've tried it, works very well, at least the "sort -m" is worthy to try. (Note: -merge is actually sort instead of merge. Here is what 'info sort' says:

`--merge'
Merge the given files by sorting them as a group. Each input file
must always be individually sorted. It always works to sort
instead of merge; merging is provided because it is faster, in the
case where it works.

2. "quicksort" http://www.bashguru.com/2011/01/quicksort-shell-script.html

This is another implementation for quicksort in bash. I've not tested it yet.

3. BSD seems already have lib for other quick sorting algorithms:

http://www.unix.com/man-page/freebsd/3/qsort/

Uniq and basic set theory

Reference: Uniq and basic set theory » Linux by Examples

Imagine that I have two files:
aquatic - contains a list of aquatic animals
starfish
whale
nemo
crab
dolphin
mammal - contains a list of mammals
whale
RMS
batman
dolphin
scooby-doo

Given aquatic and mammal are two different sets, let’s use sort and uniq to play with a few basic set theory operations:
Union ( A U B - members in either A or B )
aquatic U mamal= {batman, crab, dolphin, nemo, RMS, scooby-doo, starfish, whale}
sort aquatic mammal | uniq
Intersection ( A ∩ B - members in both A and B )
aquatic ∩ mammal = {dolphin, whale}
sort aquatic mammal | uniq -d
Symmetric Difference ( A ^ B - members in A or B but not both )
aquatic ^ mammal = {batman, crab, nemo, RMS, scooby-doo, starfish}
sort aquatic mammal | uniq -u
Relative Complement ( A \ B - members in A but not in B )
aquatic \ mammal = {crab, nemo, starfish}
sort aquatic mammal | uniq -d | sort aquatic - | uniq -u

• "sort aquatic mammal | uniq -d" performs an intersection: aquatic ∩ mammal = {dolphin, whale}.
• "sort aquatic - | uniq -u” performs a symmetric difference: aquatic ^ {dolphin, whale} = {crab, nemo, starfish}.

UPDATED: I found a piece of clean elegant codes to perform relative complement:
sort aquatic mammal mammal | uniq -u
.
“sort -u”: a short-hand for “sort | uniq”
sort -u is equivalent to sort | uniq to eliminate duplicated elements in a list. Therefore, you may replace:
sort aquatic mammal | uniq
with:
sort -u aquatic mammal
 this is quite useful when I want to do operation like AND, OR, or +/-, for example, I want to subtract file1 by file2:
sort file1 file2 | uniq -u // output all lines which are not in file1 or file2
if there are duplicated lines in file1/file2, then it's safer to use:
sort file1 file2 file2 | uniq -u

sorting BAM makes the file smaller

Yes, it's not just me to notice this change. See here: http://seqanswers.com/forums/archive/index.php/t-13652.html

As Heng said, "BAM is compressed. Sorting helps to give a better compression ratio because similar sequences are grouped together."... So it's not because of the removal of the unmapped reads (which are put at the end).

The tips is - always sort the output BAM after converting a SAM, e.g.

samtools view -Sbu in.sam | samtools sort - in.sorted

mv in.sorted.bam in.bam

Sorted BAM is smaller and better for searching. 

---------------------------

Other tips are:

1. SAM->BAM does not require a sorted header, nor a header. 

If there is header, samtools view -Sb in.sam > in.bam

if there is no header, samtools view -Sbt genome.fa.fai in.sam > in.bam

But the in.bam will not follow the order in the sequence dictionary (genome.fa.fai) unless you sort it by samtools sort. 

2. If input BAM, cufflinks require a proper header for the BAM file, esp. the line of 

@HD VN:1.0 SO:coordinate

Without the line, even if your BAM (or SAM) is sorted, but cufflinks cannot tell it by the file, only if you provide the info through the @HD line. So, I guess 

@HD VN:1.0 SO:unsorted 

won't work. 

Remove duplicate lines in a text file with uniq

After sorting a file you will often find that some duplicate data, or you may be given various lists that need de-duplicating. sort and uniq will quickly and easily remove duplicates, list only the duplicates or only the unique data:

sort myfile.txt | uniq

List only the unique lines: sort myfile.txt | uniq -u

List only the duplicate lines: sort myfile.txt | uniq -d

Get a count of the number of lines by adding the -c option.

sort myfile.txt | uniq -uc

sort myfile.txt | uniq -dc

Skip fields: uniq -f 3 mylogfile. this could be useful with log files to skip the time stamp data

Skip characters. uniq -s 30 myfile.txt. Skip the first 30 characters

Compare characters. uniq -w 30 myfile.txt. Compare the first 30 characters