Преобразование Берроуза – Уиллера

Преобразование Берроуза – Уиллера
Сорт	предварительная обработка для сжатия без потерь
Структура данных	нить
Худшая производительность	На )
Наихудшая пространственная сложность	На )

Преобразование Берроуза -Уиллера ( BWT , также называемое сжатием с сортировкой блоков ) переупорядочивает строку символов в серии похожих символов. Это полезно для сжатия, так как обычно легко сжать строку, содержащую повторяющиеся символы, с помощью таких методов, как преобразование перемещения вперед и кодирование длины серии . Что еще более важно, преобразование является обратимым , без необходимости сохранять какие-либо дополнительные данные, кроме позиции первого исходного символа. Таким образом, BWT представляет собой «бесплатный» метод повышения эффективности алгоритмов сжатия текста, требующий лишь некоторых дополнительных вычислений. Преобразование Берроуза-Уиллера — это алгоритм, используемый для подготовки данных для использования с методами сжатия данных, такими как bzip2 . Он был изобретен Майклом Берроузом и Дэвидом Уилером в 1994 году, когда Берроуз работал в исследовательском центре DEC Systems в Пало-Альто , Калифорния. Он основан на ранее неопубликованном преобразовании, открытом Уилером в 1983 году. Алгоритм можно эффективно реализовать с помощью суффиксный массив , таким образом достигая линейной временной сложности. ^{[ 1 ]}

Описание

Когда строка символов преобразуется с помощью BWT, преобразование меняет порядок символов. Если исходная строка имела несколько часто встречающихся подстрок, то в преобразованной строке будет несколько мест, где один и тот же символ повторяется несколько раз подряд.

Например:

Вход	`SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES`
Выход	`TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT`^{[ 2 ]}

Вывод легче сжать, поскольку он содержит много повторяющихся символов. В этом примере преобразованная строка содержит шесть серий одинаковых символов: XX, SS, PP, .., II, и III, которые вместе составляют 13 из 44 символов.

Пример

Преобразование осуществляется путем сортировки всех циклических сдвигов текста в лексикографическом порядке и извлечения последнего столбца и индекса исходной строки из набора отсортированных перестановок. S.

Учитывая входную строку S = ^BANANA$ (шаг 1 в таблице ниже), поверните его N раз (шаг 2), где N = 8 это длина S строка, учитывая также красный цвет ^ символ, обозначающий начало строки и красный $ символ, представляющий указатель « EOF »; эти вращения или круговые сдвиги затем сортируются лексикографически (шаг 3). Результатом фазы кодирования является последний столбец L = BNN^AA$A после шага 3 и индекс (отсчет от 0) I строки, содержащей исходную строку S, в этом случае I = 6.

Не обязательно использовать оба $ и ^, но должен использоваться хотя бы один, иначе мы не сможем инвертировать преобразование, поскольку все круговые перестановки строки имеют одно и то же преобразование Берроуза-Уиллера.

Трансформация

1. Ввод

2. Все
вращения

3. Сортировать по
лексический порядок

4. Возьмите
последний столбец

5. Выход

^BANANA$

^BANANA$
$^BANANA
A$^BANAN
NA$^BANA
ANA$^BAN
NANA$^BA
ANANA$^B
BANANA$^

ANANA$^B
ANA$^BAN
A$^BANAN
BANANA$^
NANA$^BA
NA$^BANA
^BANANA$
$^BANANA

ANANA$^B
ANA$^BAN
A$^BANAN
BANANA$^
NANA$^BA
NA$^BANA
^BANANA$
$^BANANA

BNN^AA$A

Следующий псевдокод дает простой (хотя и неэффективный) способ расчета BWT и обратного ему значения. Предполагается, что входная строка s содержит специальный символ «EOF», который является последним символом и больше нигде в тексте не встречается.

function BWT (string s)
    create a table, where the rows are all possible rotations of s
    sort rows alphabetically
    return (last column of the table)

function inverseBWT (string s)
    create empty table
    repeat length(s) times
        // first insert creates first column
        insert s as a column of table before first column of the table
        sort rows of the table alphabetically
    return (row that ends with the 'EOF' character)

Объяснение

Чтобы понять, почему это создает более легко сжимаемые данные, рассмотрите возможность преобразования длинного текста на английском языке, часто содержащего слово «the». При сортировке вращений этого текста вращение, начинающееся с «он», группируется вместе, а последним символом этого вращения (который также является символом перед «он») обычно будет «t», поэтому результат преобразования будет содержать несколько символов «t» вместе с, возможно, менее распространенными исключениями (например, если оно содержит «боль»), смешанными. Таким образом, можно видеть, что успех этого преобразования зависит от одного значения, которое с высокой вероятностью произойдет раньше последовательность, так что в целом нужны довольно длинные сэмплы (минимум несколько килобайт) соответствующих данных (например, текста).

Замечательная особенность BWT не в том, что он генерирует более легко кодируемые выходные данные (обычная сортировка сделала бы это), а в том, что он делает это обратимо , позволяя повторно сгенерировать исходный документ из данных последнего столбца.

Обратное можно понять так. Возьмите итоговую таблицу алгоритма BWT и сотрите все столбцы, кроме последнего. Имея только эту информацию, вы можете легко восстановить первый столбец. В последнем столбце указаны все символы текста, поэтому просто отсортируйте эти символы в алфавитном порядке, чтобы получить первый столбец. Затем последний и первый столбцы (каждой строки) вместе дают вам все пары последовательных символов в документе, причем пары выбираются циклически, так что последний и первый символ образуют пару. Сортировка списка пар дает первый и второй столбцы. Продолжая таким же образом, вы сможете восстановить весь список. Тогда строка с символом «конец файла» в конце является исходным текстом. Обращение приведенного выше примера делается следующим образом:

Обратное преобразование
Вход
BNN^AA$A
Добавить 1	Сортировать 1	Добавить 2	Сортировать 2
B N N ^ A A $ A	A A A B N N ^ $	BA NA NA ^B AN AN $^ A$	AN AN A$ BA NA NA ^B $^
Добавить 3	Сортировать 3	Добавить 4	Сортировать 4
BAN NAN NA$ ^BA ANA ANA $^B A$^	ANA ANA A$^ BAN NAN NA$ ^BA $^B	BANA NANA NA$^ ^BAN ANAN ANA$ $^BA A$^B	ANAN ANA$ A$^B BANA NANA NA$^ ^BAN $^BA
Добавить 5	Сортировать 5	Добавить 6	Сортировать 6
BANAN NANA$ NA$^B ^BANA ANANA ANA$^ $^BAN A$^BA	ANANA ANA$^ A$^BA BANAN NANA$ NA$^B ^BANA $^BAN	BANANA NANA$^ NA$^BA ^BANAN ANANA$ ANA$^B $^BANA A$^BAN	ANANA$ ANA$^B A$^BAN BANANA NANA$^ NA$^BA ^BANAN $^BANA
Добавить 7	Сортировать 7	Добавить 8	Сортировать 8
BANANA$ NANA$^B NA$^BAN ^BANANA ANANA$^ ANA$^BA $^BANAN A$^BANA	ANANA$^ ANA$^BA A$^BANA BANANA$ NANA$^B NA$^BAN ^BANANA $^BANAN	BANANA$^ NANA$^BA NA$^BANA ^BANANA$ ANANA$^B ANA$^BAN $^BANANA A$^BANAN	ANANA$^B ANA$^BAN A$^BANAN BANANA$^ NANA$^BA NA$^BANA ^BANANA$ $^BANANA
Выход
^BANANA$

Оптимизация

Ряд оптимизаций может сделать эти алгоритмы более эффективными без изменения выходных данных. Нет необходимости представлять таблицу ни в кодере, ни в декодере. В кодировщике каждая строка таблицы может быть представлена одним указателем на строки, а сортировка осуществляется с помощью индексов. В декодере также нет необходимости хранить таблицу, да и вообще никакая сортировка не нужна. За время, пропорциональное размеру алфавита и длине строки, декодированная строка может генерироваться по одному символу справа налево. «Символом» в алгоритме может быть байт, бит или любой другой удобный размер.

Можно также заметить, что математически закодированная строка может быть вычислена как простая модификация суффиксного массива , а суффиксные массивы могут быть вычислены с линейным временем и памятью. BWT может быть определен относительно суффиксного массива SA текста T как (индексация на основе 1):

$BWT[i]={\begin{cases}T[SA[i]-1],&{\text{if }}SA[i]>0\\\$,&{\text{otherwise}}\end{cases}}$ ^{[ 3 ]}

Нет необходимости иметь настоящий символ «EOF». Вместо этого можно использовать указатель, который запоминает, где в строке находился бы «EOF», если бы он существовал. В этом подходе выходные данные BWT должны включать как преобразованную строку, так и конечное значение указателя. Затем обратное преобразование сжимает его до исходного размера: ему присваивается строка и указатель, и он возвращает только строку.

Полное описание алгоритмов можно найти в статье Берроуза и Уиллера или в ряде интернет-источников. ^{[ 1 ]} Алгоритмы несколько различаются в зависимости от того, используется ли EOF и в каком направлении выполнялась сортировка. Фактически, в исходном составе не использовался маркер EOF. ^{[ 4 ]}

Биективный вариант

Поскольку любое вращение входной строки приведет к той же преобразованной строке, BWT нельзя инвертировать без добавления маркера EOF в конец ввода или выполнения чего-то эквивалентного, позволяющего отличить входную строку от всех ее вращений. Увеличение размера алфавита (путем добавления символа EOF) делает последующие этапы сжатия неудобными.

Существует биективная версия преобразования, при которой преобразованная строка однозначно идентифицирует оригинал, причем обе строки имеют одинаковую длину и содержат одни и те же символы, только в разном порядке. ^{[ 5 ]}^{[ 6 ]}

Биективное преобразование вычисляется путем разложения входных данных на невозрастающую последовательность слов Линдона ; такая факторизация существует и уникальна по теореме Чена – Фокса – Линдона , ^{[ 7 ]} и может быть найден в линейном времени и постоянном пространстве. ^{[ 8 ]} Алгоритм сортирует вращения всех слов; как и в преобразовании Берроуза-Уиллера, это создает отсортированную последовательность из n строк. Преобразованная строка затем получается путем выбора последнего символа каждой строки в этом отсортированном списке. Единственное важное предостережение заключается в том, что строки разной длины не упорядочиваются обычным способом; две строки повторяются вечно, а бесконечные повторы сортируются. Например, «ORO» предшествует «OR», потому что «OROORO...» предшествует «OROROR...».

Например, посредством этих шагов текст « ^ BANANA $ » преобразуется в «ANNBAA ^ $ » (красный $ символ указывает на указатель EOF ) в исходной строке. Символ EOF не нужен в биективном преобразовании, поэтому он удаляется во время преобразования и снова добавляется на свое место в файле.

Строка разбивается на слова Линдона, поэтому слова в последовательности уменьшаются с использованием описанного выше метода сравнения. (Обратите внимание, что мы сортируем ' ^ ' как последующие символы.) " ^ BANANA" становится ( ^ ) (B) (AN) (AN) (A).

Биективное преобразование

Вход

Все
вращения

Сортировано по алфавиту

Последний столбец
повернутого слова Линдон

Выход

^BANANA$

^^^^^^^^... (^)
BBBBBBBB... (B)
ANANANAN... (AN)
NANANANA... (NA)
ANANANAN... (AN)
NANANANA... (NA)
AAAAAAAA... (A)

AAAAAAAA... (A)
ANANANAN... (AN)
ANANANAN... (AN)
BBBBBBBB... (B)
NANANANA... (NA)
NANANANA... (NA)
^^^^^^^^... (^)

AAAAAAAA... (A)
ANANANAN... (AN)
ANANANAN... (AN)
BBBBBBBB... (B)
NANANANA... (NA)
NANANANA... (NA)
^^^^^^^^... (^)

ANNBAA^$

Обратное биективное преобразование
Вход
ANNBAA^
Добавить 1	Сортировать 1	Добавить 2	Сортировать 2
A N N B A A ^	A A A B N N ^	AA NA NA BB AN AN ^^	AA AN AN BB NA NA ^^
Добавить 3	Сортировать 3	Добавить 4	Сортировать 4
AAA NAN NAN BBB ANA ANA ^^^	AAA ANA ANA BBB NAN NAN ^^^	AAAA NANA NANA BBBB ANAN ANAN ^^^^	AAAA ANAN ANAN BBBB NANA NANA ^^^^
Выход
^BANANA

Вплоть до последнего шага процесс идентичен обратному процессу Берроуза – Уиллера, но здесь он не обязательно будет давать вращения одной последовательности; вместо этого он дает ротацию слов Линдона (которая начнет повторяться по мере продолжения процесса). Здесь мы можем видеть (повторения) четырех разных слов Линдона: (A), (AN) (дважды), (B) и ( ^ ). (НАНА... не представляет собой отдельное слово, поскольку это цикл АНАН....) На этом этапе эти слова сортируются в обратном порядке: ( ^ ), (B), (AN), (AN), (A). Затем они объединяются, чтобы получить

^ БАНАН

Преобразование Берроуза-Уиллера действительно можно рассматривать как частный случай этого биективного преобразования; вместо традиционного введения новой буквы из-за пределов нашего алфавита для обозначения конца строки мы можем ввести новую букву, которая сравнивается со всеми существующими буквами, которые помещаются в начале строки. Вся строка теперь является словом Линдона, и поэтому прохождение ее через биективный процесс приведет к преобразованному результату, который при инвертировании возвращает слово Линдона без необходимости повторной сборки в конце.

Соответственно, преобразованный текст будет отличаться от результата BWT только на один символ на слово Линдона; например, если входные данные разложены на шесть слов Линдона, выходные данные будут отличаться только шестью символами. Например, применение биективного преобразования дает:

Вход	`SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES`
слова Линдона	`SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES`
Выход	`STEYDST.E.IXXIIXXSMPPXS.B..EE..SUSFXDIOIIIIT`

Биективное преобразование включает восемь серий идентичных персонажи. Эти прогоны по порядку: XX, II, XX, PP, .., EE, .., и IIII.

Всего в этих прогонах используется 18 символов.

Динамическое преобразование Берроуза – Уиллера

Когда текст редактируется, его преобразование Берроуза-Уиллера изменится. Салсон и др. ^{[ 9 ]} предложить алгоритм, который выводит преобразование Берроуза-Уиллера отредактированного текста из исходного текста, выполняя ограниченное количество локальных переупорядочений в исходном преобразовании Берроуза-Уиллера, что может быть быстрее, чем построение преобразования Берроуза-Уиллера отредактированного текста. текст напрямую.

Пример реализации

В этой реализации Python жертвуется скоростью ради простоты: программа короткая, но занимает больше линейного времени, чем хотелось бы в практической реализации. По сути, он делает то же, что и раздел псевдокода.

Используя управляющие коды STX/ETX для обозначения начала и конца текста, а также используя s[i:] + s[:i] построить iй оборот sпрямое преобразование принимает последний символ каждой отсортированной строки:

from curses.ascii import STX, ETX

def bwt(s: str, start=chr(STX), end=chr(ETX)) -> str:
    r"""
    Apply Burrows–Wheeler transform to input string.

    >>> bwt('BANANA')
    '\x03ANNB\x02AA'
    >>> bwt('BANANA', start='^', end='$')
    'ANNB^AA$'
    >>> bwt('BANANA', start='%', end='$')
    'A$NNB%AA'
    """
    assert (
        start not in s and end not in s
    ), "Input string cannot contain STX and ETX characters"
    s = f"{start}{s}{end}"  # Add start and end of text marker

    # Table of rotations of string
    table = sorted(f"{s[i:]}{s[:i]}" for i, c in enumerate(s))
    last_column = [row[-1:] for row in table]  # Last characters of each row
    return "".join(last_column)  # Convert list of characters into string

Обратное преобразование многократно вставляет r в качестве левого столбца таблицы и сортирует таблицу. После того, как вся таблица построена, она возвращает строку, оканчивающуюся на ETX, за вычетом STX и ETX.

def inverse_bwt(r: str, start=chr(STX), end=chr(ETX)) -> str:
    r"""
    Apply inverse Burrows–Wheeler transform.

    >>> inverse_bwt('\x03ANNB\x02AA')
    'BANANA'
    >>> inverse_bwt('ANNB^AA$', start='^', end='$')
    'BANANA'
    >>> inverse_bwt('A$NNB%AA', start='%', end='$')
    'BANANA'
    """
    str_len = len(r)
    table = [""] * str_len  # Make empty table
    for _ in range(str_len):
        table = sorted(rc + tc for rc, tc in zip(r, table))  # Add a column of r

    # Iterate over and check whether last character ends with ETX or not
    s = next((row for row in table if row.endswith(end)), "")

    # Retrieve data from array and get rid of start and end markers
    return s.rstrip(end).strip(start)

Следуя примечаниям по реализации от Манзини, вместо этого можно использовать простой суффикс нулевого символа . Сортировку следует производить в колексикографическом порядке (строка читается справа налево), т.е. sorted(..., key=lambda s: s[::-1]) в Python. ^{[ 4 ]} (Вышеупомянутые управляющие коды на самом деле не удовлетворяют требованиям, чтобы EOF был последним символом; оба кода фактически являются первыми . Тем не менее, ротация сохраняется.)

Приложения BWT

В качестве алгоритма сжатия без потерь преобразование Берроуза-Уиллера обладает тем важным качеством, что его кодирование является обратимым и, следовательно, исходные данные могут быть восстановлены из полученного сжатия. Качество алгоритма Берроуза без потерь позволило использовать различные алгоритмы с разными целями. В качестве примера можно назвать преобразование Берроуза-Уиллера, которое используется в алгоритмах выравнивания последовательностей , сжатия изображений , сжатия данных и т. д. Ниже приводится подборка некоторых применений преобразования Берроуза-Уиллера.

BWT для выравнивания последовательностей

Появление методов секвенирования нового поколения (NGS) в конце десятилетия 2000-х годов привело к новому применению преобразования Берроуза-Уиллера. В NGS ДНК фрагментируется на небольшие фрагменты, из которых секвенируются первые несколько оснований , что дает несколько миллионов «чтений», каждое из которых имеет длину от 30 до 500 пар оснований («символов ДНК»). Во многих экспериментах, например, в ChIP-Seq , задача теперь состоит в том, чтобы привести эти чтения в соответствие с эталонным геномом , то есть с известной, почти полной последовательностью рассматриваемого организма (длина которой может достигать нескольких миллиардов пар оснований). . Был опубликован ряд программ выравнивания, специализирующихся на этой задаче, которые первоначально полагались на хеширование (например, Eland , SOAP, ^{[ 10 ]} или Мак ^{[ 11 ]}). В целях снижения требований к памяти для выравнивания последовательностей было разработано несколько программ выравнивания ( Bowie , ^{[ 12 ]} твой, ^{[ 13 ]} и SOAP2 ^{[ 14 ]}), использующие преобразование Берроуза – Уиллера.

BWT для сжатия изображений

Преобразование Берроуза-Уиллера оказалось фундаментальным для приложений сжатия изображений . Например, ^{[ 15 ]} Показан конвейер сжатия, основанный на применении преобразования Берроуза – Уиллера с последующими инверсией, кодированием длин серий и арифметическими кодировщиками. Разработанный в этом случае конвейер известен как преобразование Берроуза – Уиллера с инверсионным кодером (BWIC). Показано, что результаты, показанные BWIC, превосходят производительность сжатия известных и широко используемых алгоритмов, таких как Lossless JPEG и JPEG 2000 . Показано, что BWIC превосходит их по окончательному размеру сжатия рентгеновских медицинских изображений примерно на 5,1% и 4,1% соответственно. Улучшения достигаются за счет объединения BWIC и сканирования изображения перед BWIC в вертикальном змеевидном порядке. Совсем недавно появились дополнительные работы, такие как работа ^{[ 16 ]} показали, что реализация преобразования Берроуза-Уиллера в сочетании с известным преобразованием движения вперед (MTF) обеспечивает сжатие изображений практически без потерь.

BWT для сжатия геномных баз данных

Кокс и др. ^{[ 17 ]} представил схему геномного сжатия, в которой BWT используется в качестве алгоритма, применяемого на первом этапе сжатия нескольких наборов геномных данных, включая геномную информацию человека. В их работе было предложено улучшить сжатие BWT за счет включения механизма сжатия второго этапа, называемого кодированием «то же, что и раньше» («SAP»), который использует тот факт, что суффиксы двух или более букв префикса могут быть равны. Используя механизм сжатия BWT-SAP, Cox et al. показали, что в геномной базе данных ERA015743 размером 135,5 ГБ схема сжатия BWT-SAP сжимает набор данных ERA015743 примерно на 94%, до 8,2 ГБ.

BWT для предсказания последовательности

Также было доказано, что BWT полезен для прогнозирования последовательностей, что является общей областью исследований в машинном обучении и обработке естественного языка . В частности, Ктистакис и др. ^{[ 18 ]} предложил схему прогнозирования последовательности под названием SuBSeq, которая использует сжатие данных без потерь преобразования Берроуза-Уиллера. SuBSeq использует BWT, извлекая FM-индекс и затем выполняя серию операций, называемых BackSearch, ForwardSearch, NeighborExpansion и getConsequents, для поиска прогнозов с суффиксом . Затем прогнозы классифицируются на основе веса и помещаются в массив, из которого элемент с наибольшим весом задается как прогноз алгоритма SuBSeq. Было показано, что SuBSeq превосходит современные алгоритмы прогнозирования последовательностей как с точки зрения времени обучения, так и с точки зрения точности.

Ссылки

^ Jump up to: ^а ^б Берроуз, Майкл ; Уиллер, Дэвид Дж. (10 мая 1994 г.), Алгоритм сжатия данных без потерь с сортировкой блоков , Технический отчет 124, Digital Equipment Corporation, заархивировано из оригинала 5 января 2003 г.
^ "Адриен-Могенет/скала-bwt" . Гитхаб . Проверено 19 апреля 2018 г.
^ Симпсон, Джаред Т.; Дурбин, Ричард (15 июня 2010 г.). «Эффективное построение графа ассемблерной строки с использованием FM-индекса» . Биоинформатика . 26 (12): i367–i373. doi : 10.1093/биоинформатика/btq217 . ISSN 1367-4803 . ПМЦ 2881401 . ПМИД 20529929 .
^ Jump up to: ^а ^б Манзини, Джованни (18 августа 1999 г.). «Преобразование Берроуза – Уиллера: теория и практика» (PDF) . Математические основы информатики 1999: 24-й международный симпозиум, MFCS'99, Шклярска-Поремба, Польша, 6–10 сентября 1999 г., материалы . Springer Science & Business Media. ISBN 9783540664086 . Архивировано (PDF) из оригинала 9 октября 2022 г.
^ Гил, Дж.; Скотт, Д.А. (2009), Преобразование биективной сортировки строк (PDF) , заархивировано из оригинала (PDF) 8 октября 2011 г. , получено 9 июля 2009 г.
^ Куфляйтнер, Манфред (2009), «О биективных вариантах преобразования Берроуза – Уиллера», Голуб, январь; Ждярек, Ян (ред.), Пражская конференция по стрингологии , стр. 65–69, arXiv : 0908.0239 , Bibcode : 2009arXiv0908.0239K .
^ * Лотер, М. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, том. 17, Перрен, Д.; Ройтенауэр, К.; Берстель, Дж.; Пин, Дж. Э.; Пирилло, Г.; Фоата, Д.; Сакарович Дж.; Саймон, И.; Шютценбергер, член парламента; Шоффрут, К.; Кори, Р.; Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.), Cambridge University Press , стр. 67, ISBN 978-0-521-59924-5 , Збл 0874.20040
^ Дюваль, Жан-Пьер (1983), «Факторизация слов по упорядоченному алфавиту», Journal of Algorithms , 4 (4): 363–381, doi : 10.1016/0196-6774(83)90017-2 , ISSN 0196-6774 , Збл 0532.68061 .
^ Салсон М., Лекрок Т., Леонар М., Мушард Л. (2009). «Четырехэтапный алгоритм обновления преобразования Берроуза – Уиллера» . Теоретическая информатика . 410 (43): 4350–4359. дои : 10.1016/j.tcs.2009.07.016 .
^ Ли Р; и др. (2008). «SOAP: программа выравнивания коротких олигонуклеотидов» . Биоинформатика . 24 (5): 713–714. doi : 10.1093/биоинформатика/btn025 . ПМИД 18227114 .
^ Ли Х, Руан Дж, Дурбин Р (19 августа 2008 г.). «Картирование коротких прочтений секвенирования ДНК и вызов вариантов с использованием показателей качества картирования» . Геномные исследования . 18 (11): 1851–1858. дои : 10.1101/гр.078212.108 . ПМК 2577856 . ПМИД 18714091 .
^ Лэнгмид Б., Трапнелл С., Поп М., Зальцберг С.Л. (2009). «Сверхбыстрое и эффективное для памяти выравнивание коротких последовательностей ДНК с геномом человека» . Геномная биология . 10 (3): 25 рандов. дои : 10.1186/gb-2009-10-3-r25 . ПМК 2690996 . ПМИД 19261174 .
^ Ли Х, Дурбин Р. (2009). «Быстрое и точное выравнивание короткого чтения с помощью преобразования Берроуза – Уиллера» . Биоинформатика . 25 (14): 1754–1760. doi : 10.1093/биоинформатика/btp324 . ПМК 2705234 . ПМИД 19451168 .
^ Ли Р; и др. (2009). «SOAP2: улучшенный сверхбыстрый инструмент для выравнивания короткого чтения». Биоинформатика . 25 (15): 1966–1967. doi : 10.1093/биоинформатика/btp336 . ПМИД 19497933 .
^ Коллин П., Арнавут З., Коч Б. (2015). «Сжатие медицинских изображений без потерь с использованием преобразования Берроуза – Уиллера с инверсионным кодером» . 2015 37-я ежегодная международная конференция Общества инженерии в медицине и биологии IEEE (EMBC) . Том. 2015. С. 2956–2959. дои : 10.1109/EMBC.2015.7319012 . ISBN 978-1-4244-9271-8 . ПМИД 26736912 . S2CID 4460328 .
^ Девадосс КП, Санкарагомати Б (2019). «Сжатие медицинских изображений практически без потерь с использованием блочных методов BWT – MTF и гибридных фрактальных методов сжатия» . Кластерные вычисления . 22 : 12929–12937. дои : 10.1007/s10586-018-1801-3 . S2CID 33687086 .
^ Кокс А.Дж., Бауэр М.Дж., Якоби Т., Розоне Дж. (2012). «Крупномасштабное сжатие баз данных геномных последовательностей с помощью преобразования Берроуза-Уиллера». Биоинформатика . 28 (11). Издательство Оксфордского университета: 1415–1419. arXiv : 1205.0192 . doi : 10.1093/биоинформатика/bts173 . ПМИД 22556365 .
^ Ктистакис Р., Фурнье-Вигер П., Пуглиси С.Дж., Раман Р. (2019). «Краткий прогноз последовательности на основе BWT» . Приложения баз данных и экспертных систем . Конспекты лекций по информатике. Том. 11707. стр. 91–101. дои : 10.1007/978-3-030-27618-8_7 . ISBN 978-3-030-27617-1 . S2CID 201058996 .

Внешние ссылки

Статья Марка Нельсона о BWT. Архивировано 25 марта 2017 г. на Wayback Machine.
Биективное преобразование сортировки строк, авторы Гил и Скотт. Архивировано 8 октября 2011 г. в Wayback Machine.
Openbwt-v1.5.zip Юты содержит исходный код для различных процедур BWT, включая BWTS для биективной версии.
О биективных вариантах преобразования Берроуза – Уиллера Куфляйтнера.
Сообщение в блоге и страница проекта программы и библиотеки сжатия с открытым исходным кодом на основе алгоритма Берроуза-Уиллера.
Лекция открытого курса MIT по BWT (Основы вычислительной и системной биологии)
Сортировка таблицы рейтингов (LTS) или алгоритм взвешивания для BWT Абдеррахима Хечачена

[Burrows1994-1] Jump up to: ^а ^б Берроуз, Майкл ; Уиллер, Дэвид Дж. (10 мая 1994 г.), Алгоритм сжатия данных без потерь с сортировкой блоков , Технический отчет 124, Digital Equipment Corporation, заархивировано из оригинала 5 января 2003 г.

[2] "Адриен-Могенет/скала-bwt" . Гитхаб . Проверено 19 апреля 2018 г.

[3] Симпсон, Джаред Т.; Дурбин, Ричард (15 июня 2010 г.). «Эффективное построение графа ассемблерной строки с использованием FM-индекса» . Биоинформатика . 26 (12): i367–i373. doi : 10.1093/биоинформатика/btq217 . ISSN 1367-4803 . ПМЦ 2881401 . ПМИД 20529929 .

[Manzini-4] Jump up to: ^а ^б Манзини, Джованни (18 августа 1999 г.). «Преобразование Берроуза – Уиллера: теория и практика» (PDF) . Математические основы информатики 1999: 24-й международный симпозиум, MFCS'99, Шклярска-Поремба, Польша, 6–10 сентября 1999 г., материалы . Springer Science & Business Media. ISBN 9783540664086 . Архивировано (PDF) из оригинала 9 октября 2022 г.

[5] Гил, Дж.; Скотт, Д.А. (2009), Преобразование биективной сортировки строк (PDF) , заархивировано из оригинала (PDF) 8 октября 2011 г. , получено 9 июля 2009 г.

[6] Куфляйтнер, Манфред (2009), «О биективных вариантах преобразования Берроуза – Уиллера», Голуб, январь; Ждярек, Ян (ред.), Пражская конференция по стрингологии , стр. 65–69, arXiv : 0908.0239 , Bibcode : 2009arXiv0908.0239K .

[7] * Лотер, М. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, том. 17, Перрен, Д.; Ройтенауэр, К.; Берстель, Дж.; Пин, Дж. Э.; Пирилло, Г.; Фоата, Д.; Сакарович Дж.; Саймон, И.; Шютценбергер, член парламента; Шоффрут, К.; Кори, Р.; Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.), Cambridge University Press , стр. 67, ISBN 978-0-521-59924-5 , Збл 0874.20040

[8] Дюваль, Жан-Пьер (1983), «Факторизация слов по упорядоченному алфавиту», Journal of Algorithms , 4 (4): 363–381, doi : 10.1016/0196-6774(83)90017-2 , ISSN 0196-6774 , Збл 0532.68061 .

[Salson2009-9] Салсон М., Лекрок Т., Леонар М., Мушард Л. (2009). «Четырехэтапный алгоритм обновления преобразования Берроуза – Уиллера» . Теоретическая информатика . 410 (43): 4350–4359. дои : 10.1016/j.tcs.2009.07.016 .

[Li,_R2008-10] Ли Р; и др. (2008). «SOAP: программа выравнивания коротких олигонуклеотидов» . Биоинформатика . 24 (5): 713–714. doi : 10.1093/биоинформатика/btn025 . ПМИД 18227114 .

[Li,_H2008-11] Ли Х, Руан Дж, Дурбин Р (19 августа 2008 г.). «Картирование коротких прочтений секвенирования ДНК и вызов вариантов с использованием показателей качества картирования» . Геномные исследования . 18 (11): 1851–1858. дои : 10.1101/гр.078212.108 . ПМК 2577856 . ПМИД 18714091 .

[Langmead2009-12] Лэнгмид Б., Трапнелл С., Поп М., Зальцберг С.Л. (2009). «Сверхбыстрое и эффективное для памяти выравнивание коротких последовательностей ДНК с геномом человека» . Геномная биология . 10 (3): 25 рандов. дои : 10.1186/gb-2009-10-3-r25 . ПМК 2690996 . ПМИД 19261174 .

[Li,_H2009-13] Ли Х, Дурбин Р. (2009). «Быстрое и точное выравнивание короткого чтения с помощью преобразования Берроуза – Уиллера» . Биоинформатика . 25 (14): 1754–1760. doi : 10.1093/биоинформатика/btp324 . ПМК 2705234 . ПМИД 19451168 .

[Li,_R2009-14] Ли Р; и др. (2009). «SOAP2: улучшенный сверхбыстрый инструмент для выравнивания короткого чтения». Биоинформатика . 25 (15): 1966–1967. doi : 10.1093/биоинформатика/btp336 . ПМИД 19497933 .

[Collin,_P2019-15] Коллин П., Арнавут З., Коч Б. (2015). «Сжатие медицинских изображений без потерь с использованием преобразования Берроуза – Уиллера с инверсионным кодером» . 2015 37-я ежегодная международная конференция Общества инженерии в медицине и биологии IEEE (EMBC) . Том. 2015. С. 2956–2959. дои : 10.1109/EMBC.2015.7319012 . ISBN 978-1-4244-9271-8 . ПМИД 26736912 . S2CID 4460328 .

[Devadoss,_CP2019-16] Девадосс КП, Санкарагомати Б (2019). «Сжатие медицинских изображений практически без потерь с использованием блочных методов BWT – MTF и гибридных фрактальных методов сжатия» . Кластерные вычисления . 22 : 12929–12937. дои : 10.1007/s10586-018-1801-3 . S2CID 33687086 .

[Cox,_AJ2012-17] Кокс А.Дж., Бауэр М.Дж., Якоби Т., Розоне Дж. (2012). «Крупномасштабное сжатие баз данных геномных последовательностей с помощью преобразования Берроуза-Уиллера». Биоинформатика . 28 (11). Издательство Оксфордского университета: 1415–1419. arXiv : 1205.0192 . doi : 10.1093/биоинформатика/bts173 . ПМИД 22556365 .

[Ktistakis,_R2019-18] Ктистакис Р., Фурнье-Вигер П., Пуглиси С.Дж., Раман Р. (2019). «Краткий прогноз последовательности на основе BWT» . Приложения баз данных и экспертных систем . Конспекты лекций по информатике. Том. 11707. стр. 91–101. дои : 10.1007/978-3-030-27618-8_7 . ISBN 978-3-030-27617-1 . S2CID 201058996 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]

[ 15 ]

[ 16 ]

[ 17 ]

[ 18 ]