<p>The following is only a comment to @JouniS' answer, but it is too long to fit in 512 characters.</p>

<p>The algorithm @JouniS was describing has been rediscovered multiple times. The C program below constructs BWT with this algorithm. It is proof-of-concept only, not intended for long strings.</p>

<pre class="lang-c prettyprint-override"><code>#include &lt;string.h&gt;
#include &lt;stdio.h&gt;
int str2bwt(char *s)
{
    int i, l, c = 0, k = 0;
    l = strlen(s); // length of input string
    for (i = l - 1; i &gt;= 0; --i) {
        int j, r = 0, a = s[i];
        memmove(&amp;s[i], &amp;s[i+1], k); // make room for insertion
        s[i+k] = a; // insert the char
        for (j = i; j &lt; i + k; ++j) r += (s[j] &lt;= a);
        for (; j &lt; l; ++j) r += (s[j] &lt; a);
        k = r + 1, c = a;
    }
    return k; // the position of sentinel '$'
}
int main(int argc, char *argv[])
{
    int k;
    if (argc == 1) return 1;
    k = str2bwt(argv[1]);
    fwrite(argv[1], 1, k, stdout); putchar('$'); puts(&amp;argv[1][k]);
    return 0;
}
</code></pre>

<p>PS: this is one of the simplest ways to construct BWT and does not require any additional dependencies. It is slow for long strings, though.</p>

CC BY-SA 3.0
2018-02-12T04:24:49.027Z
2018-02-12T04:24:49.027Z
user172818
<h2>Papers</h2>

<p>The space-efficient BWT construction algorithm is in <a href="https://github.com/lh3/bwa/blob/master/bwt_gen.c" rel="nofollow noreferrer">bwt_gen.c</a>. One of the first things you see there is the copyright line:</p>

<blockquote>
  <p>Copyright (C) 2004, Wong Chi Kwong.</p>
</blockquote>

<p>With that name, you can find the relevant papers:</p>

<ul>
<li>Lam et al: <a href="https://doi.org/10.1093/bioinformatics/btn032" rel="nofollow noreferrer">Compressed indexing and local alignment of DNA</a> (Bioinformatics, 2008). This paper describes the BWT-SW alignment algorithm.</li>
<li>Hon et al: <a href="http://www.siam.org/meetings/alenex04/abstacts/WHon.pdf" rel="nofollow noreferrer">Practical Aspects of Compressed Suffix Arrays and FM-index in Searching DNA Sequences</a> (ALENEX 2004). This was the first paper to demonstrate that it's feasible to build the FM-index for a human genome.</li>
<li>Hon et al: <a href="https://doi.org/10.1007/s00453-006-1228-8" rel="nofollow noreferrer">A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays</a> (Algorithmica, 2007). This paper contains the theoretical description of the construction algorithm.</li>
</ul>

<p>The third paper only mentions BWT briefly in the last section. It deals with compressed suffix arrays, which are space-efficient representations of the inverse function of LF-mapping. But if you have a representation of (the inverse of) the LF-mapping, you have a representation of the BWT. Hence the algorithm can be adapted for BWT construction.</p>

<h2>Algorithm</h2>

<p>When building BWT, you usually append a unique character <code>$</code> to the end of the text, either implicitly or explicitly. This way you can reduce sorting rotations to sorting suffixes. You sort the suffixes in lexicographic order, and then you output the preceding character for each suffix in that order to form the BWT.</p>

<p>Assume that you already have the BWT for string <code>X</code>, and you want to transform it into the BWT of string <code>cX</code>, where <code>c</code> is a single character. You can do that in three steps (this assumes 0-based array indexing):</p>

<ol>
<li>Find the position <code>i</code> of the full suffix <code>X</code>, and replace the <code>$</code> in the BWT with the inserted character <code>c</code> (set <code>BWT[i] = c</code>).</li>
<li>Determine the number of suffixes <code>j</code> that are lexicographically smaller than <code>cX</code> with <code>j = LF(i, c) = C[c] + BWT.rank(i, c)</code>. Here <code>C[c]</code> is the number of suffixes that start with a character smaller than <code>c</code>, and <code>BWT.rank(i, c)</code> is the number of occurrences of <code>c</code> in the prefix <code>BWT[0..i-1]</code>.</li>
<li>Insert <code>$</code> between <code>BWT[j-1]</code> and <code>BWT[j]</code>.</li>
</ol>

<p>By iterating this, you can build the BWT for any string slowly but space-efficiently. The algorithm of Hon et al. is based on the same idea, but they make it faster by inserting multiple characters at the same time. Given the BWT of string <code>X</code> and another string <code>Y</code>, they produce the BWT of the concatenation <code>YX</code>. The details are quite complicated, but you can find them in the third paper and in the source code.</p>

CC BY-SA 3.0
2018-02-11T18:19:18.043Z
2018-02-11T18:19:18.043Z
Jouni Sirén
<p>I need to know how BWA generate bw and sa in less memory usage. I didn't find details in the <a href="https://academic.oup.com/bioinformatics/article/25/14/1754/225615" rel="nofollow noreferrer">original paper</a>. Do they save all rotations temporary ? I need to know do BWA stores all rotations so that it can sort the rotations alphabetically ?</p>
<p>Thanks.</p>

<phylogenetics><bwa>
How BWA generate index files?
# How BWA generate index files?

(Asked by: username_0 on 2018-02-10)

I need to know how BWA generate bw and sa in less memory usage. I didn't find details in the [original paper](https://academic.oup.com/bioinformatics/article/25/14/1754/225615). Do they save all rotations temporary ? I need to know do BWA stores all rotations so that it can sort the rotations alphabetically ?

Thanks.

**Tags:** phylogenetics, bwa

---

## 2 answers

### Answer by username_2 on 2018-02-11. Score: 4 | Accepted answer

## Papers

The space-efficient BWT construction algorithm is in [bwt\_gen.c](https://github.com/lh3/bwa/blob/master/bwt_gen.c). One of the first things you see there is the copyright line:

> Copyright (C) 2004, Wong Chi Kwong.

With that name, you can find the relevant papers:

* Lam et al: [Compressed indexing and local alignment of DNA](https://doi.org/10.1093/bioinformatics/btn032) (Bioinformatics, 2008). This paper describes the BWT-SW alignment algorithm.
* Hon et al: [Practical Aspects of Compressed Suffix Arrays and FM-index in Searching DNA Sequences](http://www.siam.org/meetings/alenex04/abstacts/WHon.pdf) (ALENEX 2004). This was the first paper to demonstrate that it's feasible to build the FM-index for a human genome.
* Hon et al: [A Space and Time Efficient Algorithm for Constructing Compressed Suffix Arrays](https://doi.org/10.1007/s00453-006-1228-8) (Algorithmica, 2007). This paper contains the theoretical description of the construction algorithm.

The third paper only mentions BWT briefly in the last section. It deals with compressed suffix arrays, which are space-efficient representations of the inverse function of LF-mapping. But if you have a representation of (the inverse of) the LF-mapping, you have a representation of the BWT. Hence the algorithm can be adapted for BWT construction.

## Algorithm

When building BWT, you usually append a unique character `$` to the end of the text, either implicitly or explicitly. This way you can reduce sorting rotations to sorting suffixes. You sort the suffixes in lexicographic order, and then you output the preceding character for each suffix in that order to form the BWT.

Assume that you already have the BWT for string `X`, and you want to transform it into the BWT of string `cX`, where `c` is a single character. You can do that in three steps (this assumes 0-based array indexing):

1. Find the position `i` of the full suffix `X`, and replace the `$` in the BWT with the inserted character `c` (set `BWT[i] = c`).
2. Determine the number of suffixes `j` that are lexicographically smaller than `cX` with `j = LF(i, c) = C[c] + BWT.rank(i, c)`. Here `C[c]` is the number of suffixes that start with a character smaller than `c`, and `BWT.rank(i, c)` is the number of occurrences of `c` in the prefix `BWT[0..i-1]`.
3. Insert `$` between `BWT[j-1]` and `BWT[j]`.

By iterating this, you can build the BWT for any string slowly but space-efficiently. The algorithm of Hon et al. is based on the same idea, but they make it faster by inserting multiple characters at the same time. Given the BWT of string `X` and another string `Y`, they produce the BWT of the concatenation `YX`. The details are quite complicated, but you can find them in the third paper and in the source code.


---

### Answer by username_1 on 2018-02-12. Score: 3

The following is only a comment to @JouniS' answer, but it is too long to fit in 512 characters.
The algorithm @JouniS was describing has been rediscovered multiple times. The C program below constructs BWT with this algorithm. It is proof-of-concept only, not intended for long strings.
#include 
#include 
int str2bwt(char *s)
{
    int i, l, c = 0, k = 0;
    l = strlen(s); // length of input string
    for (i = l - 1; i >= 0; --i) {
        int j, r = 0, a = s[i];
        memmove(&s[i], &s[i+1], k); // make room for insertion
        s[i+k] = a; // insert the char
        for (j = i; j < i + k; ++j) r += (s[j] <= a);
        for (; j < l; ++j) r += (s[j] < a);
        k = r + 1, c = a;
    }
    return k; // the position of sentinel '$'
}
int main(int argc, char *argv[])
{
    int k;
    if (argc == 1) return 1;
    k = str2bwt(argv[1]);
    fwrite(argv[1], 1, k, stdout); putchar('$'); puts(&argv[1][k]);
    return 0;
}

PS: this is one of the simplest ways to construct BWT and does not require any additional dependencies. It is slow for long strings, though.


---

