K-Mer Counting And Constructing Bwt Index In String Graph Assembler (Sga)

Question

[ugly.betty77]

While going through the code of string graph assembler (SGA) and especially Heng Li's implementation of BCR algorithm for fast indexing of sequence libraries (https://raw.github.com/lh3/ropebwt/master/bcr.c), I came to realize that constructing Burrows Wheeler transform in SGA has many similarities with k-mer counting in de Bruijn graph-based genome assembler. In my naive understanding of BWT (but not BCR code), constructing BWT index is likely to take more time in regions with highly repetitive k-mers. Does anyone has further insight into the process? Are these kind of code and algorithm-related questions appropriate for Biostar?

[Neilfws]

Yes, bioinformatics code and algorithm questions are entirely appropriate. It helps if questions are specific, "further insight into the process" is rather vague.

Answer 1

[Ketil]

Although I'm not an expert on this, constructing the BWT is essentially the same as constructing a suffix array. Since there are linear time algorithms for this, I don't think repetitive regions will necessarily be slower. But it is possible that there are other algorithms that are used because they are faster in practice, but slow down in specific cases (much like quicksort).

[ugly.betty77]

"Since there are linear time algorithms for this"

Thank you Ketil. I do not think the matter is that simple. Constructing BWT for a large read library is not trivial and a number of papers came out last year, mostly from Anthony Cox and colleagues. Heng Li released his ropebwt2 algorithm a week back related to the same topic, but I have not got time to study it in enough detail to comment.

---