Build a table of unique lines in a file and the number of times each unique line was observed

Question

I have a file, file.txt of DNA sequences, where each line is a DNA sequence. The first 5 lines look like this:

GACAGAGGGTGCAAACGTTGTTCGGAATTACTGGGCGTAAAGCGCGTGTAGGCGGCCATGCAAGTCGGATGTGAAAGCCCTCGGCTCAACCGGGGAAGTGCACTCGAAACTGCAAGGCTAGAGTCTCGGAGAGGATCGTGGAATTCTCGGTGTAGAGGTGAAATTCGTAGATATCGAGAGGAACACCGGTGGCGAAGGCGGCGATCTGGACGATGACTGACGCTGAGACGCGAAAGCGTGGGGAGCAAACAGG
TACGTAGGGTGCGAGCGTTAATCGGAATTACTGGGCGTAAAGCGTGCGCAGGCGGTCTCGTAAGCTGGGTGTGAAAGCCCCGGGCTTAACCTGGGAATGGCATTCAGGACTGCGAGGCTCGAGTGTGGCAGAGGGAGGTGGAATTCCACGTGTAGCAGTGAAATGCGTAGAGATGTGGAGGAACACCGATGGCGAAGGCAGCCTCCTGGGCCAGCACTGACGCTCATGCACGAAAGCGTGGGGAGCAAACAGG
GACGTGTGAGGCAAGCGTTATTCGTCATTAATGGGTTTAAAGGGTACGTAGGCGGAATACTTTATTATGTTTAAGAAGACACTTAAAAGTGAACATGATAATAAAATTCTAGAGTTTGAAAGGAGTAAACAATTACCTCGAGAGTAAGGGACAACTAATACGGAAATACTTGGGGGGATTCTAAGCGGCGAAAGCATGTTACTATTGAAAACTGACGCTGAGGTACGAAGGCTTGGGTATCGACTGGG
TACGAAGGGTGCAAACGTTGCTCGGAATTATTGGGCGTAAAGCGCATGTAGGCGGCTTAGCAAGTCGGATGTGAAATCCCTCGGCTCAACCAAGGAAGTGCATCCGAAACTGCTGAGCTTGAGTACGAAAGAGGATCGCGGAATTCCCGGTGTAGAGGTGAAATTCGTAGATATCGGGAGGAACACCAGTGGCGAAGGCGGCGATCTGGGTCGATACTGACGCTGAGGTGCGAAAGCGTGGGGAGCAAACAGG
AACGTAGGAGACAAACGTTATCCGGAGTTACTGGGCGTAAAGGGCGTGTAGGTGGTTGCGTAAGTCTGGCGTGAAATTTTTCGGCTTAACCGGGAAAGGTCGTCGGATACTGCGTAGCTAGAGGACGGTAGAGGCGTGTGGAATTCCGGGGGTAGTGGTGAAATGCGTAGAGATCCGGAGGAACACCAGTGGCGAAGGCGACACGCTGGGCCGTACCTGACACTGATGCGCGACAGCATGGGGAGCAAACACT

The actual file contains tens of thousands of lines. I would like to identify all the unique sequences in this file (or the unique lines) and the number of times each sequence (or line) was observed in the file. Ideally this would be returned as a matrix with one column in R where the entries are the sequence abundances and the rownames are the unique sequences.

Alternatively, this could write out to a .csv file where the first line is a comma separated string of the unique sequences (lines) and the second line is a comma separated string of the number of times each sequence occurs in the file.

Second, this file is large-ish (~5 MB), but there are many files like it. Downstream I will have to merge many of these vectors together. How can I generate this vector while minimizing memory usage?

Answer 1

EDIT

I didn't know Unix answers were allowed. So the following is two alternatives for sort | uniq answers. Considering your files are in the same folder, named myFile_1.txt myFile_2.txt myFile_n.txt

The best in my tests with 700k lines 160Mb:

perl -ne '$count{$_}++; END { print "$count{$_} $_" for sort {$count{$b} <=> $count{$a} || $b cmp $a} keys %count}' myFile*.txt > output.txt

A more detailed explanation can be found here.

And an alternative that differs because does not have to actually sort the file (but if you have too many different keys, it will use more memory).

cat myFile*.txt | awk '{ cnts[$0] += 1 } END { for (v in cnts) print cnts[v], v }' > output.txt

A more detailed explanation can be found here.

Previous R answer

You can put your data in a vector struture like this:

data <- c("GACAGAG", "TACGTAGG", "AACGTAGG", "GACGTGTG", "TACGAAGG", "AACGTAGG")
ans <- table(data)
ans["AACGTAGG"]

5MB fits in your memory, so I guess it will work. However, if you have some data that does not fit in the memory, you will have to process the file line by line or use some solution like SparkR.

Hope it helps :)

Answer 2

Are you working on a Unix system? (This answer won't work on Windows out of the box)

I created a file named testtext.txt with the content as follows:

c
a
b
a
b
b
b
c

Then executing the following command in the terminal

sort testtext.txt | uniq -c > testcounts.txt

generates a file, testcounts.txt with the content below.

2 a
4 b
2 c

I cant speak to how this will perform relative to other solutions, but seems be worth a shot.

You could also do it simultaneously across all files matching a pattern in the current directory - I made three - testtext.txt, testtext2.txt, and testtext3.txt

find . -type f -name 'testtext*' | xargs sort | uniq -c > Counts.txt

then creates the file Counts.txt

10 a
 6 b
 5 c
 3 d
 1 e
 1 f

Alternatively (and particularly if memory usage is of concern) you could put the single file example in a simple bash script for loop to handle files one at a time. Either way, the Unix command line tools are shockingly efficient when used elegantly.

Credit: Unix.StackExchange: Sort and Count Number of Occurence of Lines on

Answer 3

Just using R base commands compare the results for 500000 rows of data:

Here is our test file, 500K rows, 122MB.

wc -l myFile.txt
# 500000 myFile.txt

ls -lh myFile.txt
# xxx xxx xxx xxx 122M May 10 09:05 myFile.txt

Using sort | uniq:

time sort myFile.txt | uniq -c > myFileCounts1.txt

# real    0m7.317s
# user    0m12.998s
# sys     0m0.228s

Using R, table (from related post):

system.time(write.table(table(readLines("myFile.txt")), "myFileCounts2.txt",
                        col.names = FALSE, row.names = FALSE , quote = FALSE))

#  user  system elapsed
# 3.028   0.100   3.142

Answer 4

You should use a HashMap with your sequences are the keys and the values an Integer that counts the number of appearances.

The algorithm in java pseudo code would be as follows, reading lines til EOF

Map<String, Integer> map = new Map...
String line;
Integer appearances;

while(not EOF)
    line = read line however suits your problem
    appearances = map.get(line)
    if(appearances == null)
        map.put(line, 1)
    else
        map.put(line, appearances+1)

Then you can access all the lines you've and their values by consulting the map keyset and doing gets or just using the entryset

Regarding efficency, you probably can't get a more efficient method than using a dictionary in this way.