= Solution
A <cyclic rotation> moves the first character to the end without changing the cyclic order of the remaining characters. Starting with the specified terminator-first row and repeatedly rotating left gives the following <matrix>; its row order is only a construction order, not a sorting order:
$$
R=\begin{pmatrix}
\char36{}&A&C&A&A&C&G\\
A&C&A&A&C&G&\char36{}\\
C&A&A&C&G&\char36{}&A\\
A&A&C&G&\char36{}&A&C\\
A&C&G&\char36{}&A&C&A\\
C&G&\char36{}&A&C&A&A\\
G&\char36{}&A&C&A&A&C
\end{pmatrix}.
$$
Under <lexicographic order>, compare characters from left to right, using $\char36{}\lt A\lt C\lt G$. The sorted <cyclic rotation> <matrix> is therefore
$$
B=\begin{pmatrix}
\char36{}&A&C&A&A&C&G\\
A&A&C&G&\char36{}&A&C\\
A&C&A&A&C&G&\char36{}\\
A&C&G&\char36{}&A&C&A\\
C&A&A&C&G&\char36{}&A\\
C&G&\char36{}&A&C&A&A\\
G&\char36{}&A&C&A&A&C
\end{pmatrix}.
$$
The <Burrows-Wheeler transform> is the last column, read downwards, so \b[the transformed string] is
$$
\boxed{\operatorname{BWT}(S_1)=\texttt{GC\char36{}AAAC}}.
$$
Back to article page
