The Burrows-Wheeler Transform
Статья в интерактивном формате объясняет, как работает Burrows-Wheeler Transform (BWT) — алгоритм, который лежит в основе сжатия bzip2 и инструментов выравнивания последовательностей bowtie/bwa. Суть BWT в том, что он группирует идентичные символы, а затем позволяет точно восстановить исходную строку. Для демонстрации автор кодирует слово «banana» и показывает, как появление символа $ вращает матрицу, делая обратное преобразование возможным. В статье также показано, как поиск подстроки сводится к просмотру первого и последнего столбцов, и как это используется в биоинформатике для выравнивания ДНК-чтения.