Transformata Burrowsa-Whelera: Odwracalne Przemieszczenie Za Lewem bzip2 i Wyszukiwania Genomowych

Budowanie Transformacji: Rotacje i Sortowanie

Transformata Burrowsa-Whelera rozpoczyna się od jednego triku zaczerpniętego z teorii strun: rotacji cyklicznej. Biorąc pod uwagę dany ciąg znaków, dodaje się unikalny znak sentynekstu, który jest gwarantowany jako mniejszy niż każdy inny znak w alfabecie, często zapisywany jako specjalny symbol. Ten sentynekst oznaczający prawdziwe zakończenie ciągu i, co najważniejsze, zapewnia, że żadna rotacja nie jest nigdy identyczna z inną, co czyni krok sortowania dobrze zdefiniowany. Z tego ciągu oznaczonego sentynekstem generuje się wszystkie rotacje cykliczne: brany jest ciąg, pierwszy znak przemieszcza się na koniec, a ten proces powtarza się aż do wygenerowania tak wielu rotacji, jak liczba znaków w ciągu, w tym sentynekst. Po wygenerowaniu wszystkich rotacji ułada się je w macierz i sortuje się wiersze leksykograficznie, czyli w kolejności słownikowej przy użyciu zasad porównawczych alfabetu. Ta uporządkowana ułożenie jest często nazywana Macierzą Burrowsa-Whelera. Ponieważ sentynekst jest zdefiniowany jako mniejszy niż każdy inny znak, zawsze sortuje się tak, aby zajmował pierwszy wiersz, gdy pojawia się na początku rotacji, co zakotwicza całą strukturę i umożliwia jej późniejsze odwrócenie. Transformata sama składa się z ostatniej kolumny tej posortowanej macierzy, czytanej od góry do dołu. Ta pojedyncza kolumna stanowi pełny wynik transformaty Burrowsa-Whelera. Zauważ, co wydarzyło się strukturalnie: pierwszy wiersz uporządkowanej macierzy to po prostu znaki oryginalnego ciągu posortowane alfabetycznie, a ostatnia kolumna to przekształcenie zdeterminowane przez to, jaki znak poprzedzał kontekst każdej rotacji. Ponieważ sortowanie grupuje wszystkie rotacje rozpoczynające się od tego samego podciągu, znaki tuż przed tymi współdzielonymi podcięgami, które znajdują się w ostatniej kolumnie, często powtarzają się. To jest cała mechaniczna przyczyna pojawienia się grupowania: podobne konteksty sortowane są obok siebie, a znak kończący każdy z tych podobnych kontekstów ma tendencję do bycia tym samym znakiem powtarzanym. Transformata wymienia ciąg z rozproszonymi powtórzeniami na ten z zgrupowanymi powtórzeniami, bez utraty pojedynczego bitu informacji potrzebnej do odwrócenia tego procesu.

Dlaczego grupowanie ułatwia kompresję

Transformata Burrowsa-Whelera nie kompresuje danych samodzielnie; przekształca dane w formę, która jest znacznie łatwiejsza do skompresowania dla prostszych algorytmów. To rozróżnienie ma znaczenie. Transformata jest zawsze połączona z niewielkim zestawem etapów przetwarzania kolejnych, a zrozumienie, dlaczego każdy etap korzysta z tego przekształcenia, wyjaśnia cały projekt. Pierwszym etapem przetwarzania kolejnego jest zazwyczaj kodowanie move-to-front. Ta technika utrzymuje listę wszystkich możliwych znaków i, za każdym razem, gdy znak pojawia się wejściowym, wypisuje jego obecną pozycję w liście i następnie przesuwa ten znak na początek. Gdy wejście ma długie ciągi identycznych lub podobnych znaków, co transformata Burrowsa-Whelera ma tendencję do generowania, kodowanie move-to-front produkuje długie ciągi małych liczb, zwłaszcza zer, ponieważ niedawno widziany znak prawdopodobnie pojawi się ponownie wkrótce i już będzie na początku listy. Drugim etapem jest kodowanie długości sekwencji, które wykorzystują dokładnie te długie ciągi powtarzających się małych liczb, zastępując ciąg identycznych wartości pojedynczą wartością plus licznikiem. Długi ciąg dwudziestu zer staje się tylko dwie liczby zamiast dwadzieścia. Ten etap sam w sobie może osiągnąć ogromne redukcje rozmiaru, gdy kodowanie długości sekwencji jest zdominowane przez długie ciągi, co dokładnie jest sytuacją, do której transformata Burrowsa-Whelera przygotowuje dane. Ostatnim etapem jest zazwyczaj entropijowy kodek, taki jak kodowanie Huffmana lub kodowanie arytmetyczne, zastosowany do strumienia zakodowanego długością sekwencji. Kodeki entropijne przypisują krótsze kody bardziej częstym symbolom. Ponieważ wczesniejsze etapy już skoncentrowały strukturę statystyczną danych w niewielkiej liczbie często powtarzających się małych wartości, kodek entropijny ma znacznie mniej pracy do wykonania, aby osiągnąć silną kompresję niż zrobiłby na surowym oryginalnym tekście. To kompletna łańcuch używany w bzip2: transformata Burrowsa-Whelera, kodowanie move-to-front, kodowanie długości sekwencji i następnie kodowanie Huffmana, a każdy z tych etapów istnieje specyficznie dlatego, że poprzedni etap przekształcił dane tak, aby następny etap miał łatwiejszą pracę.

Odwracanie Transformacji: Pierwsza Kolumna, Ostatnia Kolumna

Najbardziej charakterystyczną cechą transformaty Burrowsa-Whelera jest jej możliwość dokładnego odwrócenia, przywracając oryginalny ciąg znaków, znak po znaku, wykorzystując jedynie transformowany ciąg, często nazywany ostatnią kolumną, oraz pojedynczą liczbę wskazującą, która rotacja posortowana odpowiada oryginalnemu ciągowi. Nie trzeba przechowywać ani generować ponownie żadnych rotacji, co utrzymuje proces wydajny nawet dla bardzo długich ciągów, takich jak całe chromosomy. Odwracanie opiera się na relacji między pierwszą kolumną a ostatnią kolumną macierzy rotacji posortowanej opisanej wcześniej. Pamiętajmy, że pierwsza kolumna to po prostu znaki transformowanego ciągu posortowane alfabetycznie, ponieważ przedstawia ona początkowy znak każdej rotacji posortowanej. Ważny fakt strukturalny, czasem nazywany mapowaniem od ostatniej do pierwszej kolumny, mówi o tym, że względne uporządkowanie wystąpień jakiejkolwiek danej litery jest zachowane między ostatnią a pierwszą kolumną. Innymi słowy, jeśli przyjrzy się trzeciemu wystąpieniu litery, na przykład 'a', w ostatniej kolumnie, odpowiada mu również trzecie wystąpienie tej samej litery w pierwszej kolumnie, ponieważ rotacja zachodzi równomiernie we wszystkich wierszach, a sortowanie zachowuje względny porządek powiązań w stabilny sposób. Ten fakt umożliwia przejście wstecz przez oryginalny ciąg. Rozpoczynając od wiersza znanego z odpowiadania końcowi ciągu lub równoważnie używając zapisanej indeksu oryginalnej rotacji, algorytm wielokrotnie wykorzystuje mapowanie od ostatniej do pierwszej kolumny, aby przeskoczyć z pozycji litery w ostatniej kolumnie na jej odpowiadającą pozycję w pierwszej kolumnie, odczytując znaki i cofając się o jedną pozycję za każdym razem. Ponieważ pierwsza kolumna może być wyprowadzona właśnie przez posortowanie ostatniej kolumny, a mapowanie między wystąpieniami identycznych znaków można obliczyć przy użyciu prostego liczenia, cały oryginalny ciąg można odtworzyć w czasie proporcjonalnym do jego długości, wykorzystując jedynie tablice i liczby, zamiast pełnej macierzy rotacji. Ta wydajność, zarówno w kierunku przodu z technikami sortowania sufitów, jak i w tym ostrożnym kroku wstecz, sprawia, że transformacja jest praktyczna dla plików i genomów o ogromnych rozmiarach, a nie tylko ciekawostką teoretyczną.

Od kompresji danych tekstowych do wyrównywania genomów

Transformata Burrowsa-Whelera po raz pierwszy znalazła swoje główne zastosowanie w kompresji danych ogólnego przeznaczenia, przede wszystkim w utilitarzu bzip2, gdzie konsekwentnie przewyższała starsze techniki oparte na Lempel-Ziv przy wielu rodzajach tekstu i danych strukturalnych, a to właśnie dlatego, ponieważ ujawnia lokalne regularności statystyczne, których te starsze metody nie wykorzystują bezpośrednio. Jednak dziesiątki lat po jej wynalezieniu transformata znalazła zupełnie inne, a być może nawet bardziej istotne zastosowanie: wyszukiwanie ogromnych sekwencji DNA. Ludzki genom zawiera około trzech miliardów par zasad DNA, a nowoczesna technologia sekwencjonowania produkuje setki milionów krótkich fragmentów DNA, zwanych odczytami, które każde muszą zostać dopasowane do ich prawidłowej pozycji w tym genomie. Robienie tego na ślepo, skanując genom za każdym odczytem, byłoby znacznie zbyt powolne. Narzędzia takie jak BWA (Burrows-Wheeler Aligner) i Bowtie zamiast tego budują transformatę Burrowsa-Whelera całego genomu referencyjnego z wyprzedzeniem, wraz z towarzyszącą jej strukturą indeksową o nazwie FM-index, nazwanym na cześć jego twórców Paolo Ferragina i Giovanni Manzini. FM-index wykorzystuje tę samą relację od ostatniego do pierwszego, która napędza odwracanie, aby zamiast tego obsłużyć niezwykle szybkie wyszukiwanie podciągów. Rozpoczynając od pełnego zakresu wierszy macierzy obrotowej posortowanej, algorytm wyszukiwania zawęża ten zakres o jeden znak na raz, cofając się przez sekwencję zapytania, wykorzystując wstępnie obliczone liczby wystąpień każdego znaku i gdzie występują. Po przetworzeniu całego zapytania, którykolwiek pozostały zakres wierszy odpowiada dokładnie każdej pozycji w genomie, gdzie występuje ta sekwencja zapytania. To wyszukiwanie zajmuje czas proporcjonalny do długości odczytu zapytania zamiast długości genomu, co czyni je możliwym do dopasowania setek milionów odczytów do genomu wielomilionowego par zasad DNA w rozsądnym czasie. Właśnie właściwość kompresji przyjazna dla grupowania transformacji, zdaje się, jest tym samym fundamentalnym faktem, który umożliwia to szybkie wyszukiwanie genomowe.

Rozważania Praktyczne i Ograniczenia

Pomimo swojej elegancji, transformata Burrowsa-Whelera wiąże się z kosztami i ograniczeniami praktycznymi, które warto zrozumieć. Obliczanie transformaty na swój sposób, poprzez generowanie wszystkich rotacji i sortowanie ich, zajmuje czas proporcjonalny do kwadratu długości ciągu znaków lub gorzej, ponieważ każda z wielu rotacji może być porównywana charakter po charakterze z wieloma innymi. Dla krótkich ciągów znaków to nie ma znaczenia, ale dla plików o rozmiarze megabajtach lub gigabajtach, albo genomów z miliardami baz, ten naiwny sposób jest znacznie zbyt wolny. W praktyce transformata obliczana jest przy użyciu algorytmów budowania tablic sufiksowych, które tworzą powiązany posortowany strukturę w czasie, który rośnie tylko proporcjonalnie lub prawie tak, wykorzystując techniki o nazwach takich jak DC3 lub SA-IS. Transformata Burrowsa-Whelera może wtedy być wyprowadzona bezpośrednio z ukończonej tablicy sufiksowej bez konieczności materializowania pełnej macierzy rotacji, co czyni narzędzia rzeczywiste praktyczne na poziomie genomowym. Kolejne rozważanie praktyczne to rozmiar bloku. Kompresory takie jak bzip2 nie stosują transformaty do całego pliku naraz; zamiast tego dzielą dane wejściowe na bloki, często kilkaset kilobajtów każdy, i przetwarzają każdy blok niezależnie. Większe bloki generalnie pozwalają na lepszą kompresję, ponieważ wokół znaków może gromadzić się więcej kontekstu, ale również wymagają więcej pamięci i czasu przetwarzania, więc rzeczywiste implementacje zbilansowują rozmiar bloku względem tych kosztów. Warto także precyzyjnie określić, co transformata robi, a czego nie robi. Jest to bezstratne, całkowicie odwracalne przemieszczenie znaków wejściowego; sama w sobie nie usuwa ani nie przybliża żadnych informacji i sama w sobie nie osiąga żadnej kompresji. Jej wartość leży wyłącznie w reorganizacji danych w taki sposób, aby proste, szybkie i dobrze znane algorytmy, niezależnie czy to move-to-front i kodowanie długości sekwencji dla kompresji, czy też indeks FM do wyszukiwania, mogły działać skuteczniej niż na oryginalnych, nieprzetransformowanych danych.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Burrows-Wheeler Transform: The Reversible Shuffle Behind bzip2 and Genome Search i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.