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

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

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

Описание [ править ]

Преобразование Барроуза-Уиллера - это алгоритм, используемый для подготовки данных для использования с такими методами сжатия данных , как bzip2 . Его изобрели Майкл Берроуз и Дэвид Уиллер в 1994 году, когда Берроуз работал в DEC Systems Research Center в Пало-Альто , Калифорния. Он основан на ранее неопубликованном преобразовании, обнаруженном Уилером в 1983 году. Алгоритм может быть эффективно реализован с использованием массива суффиксов, что позволяет достичь линейной временной сложности. ^[1]

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

Например:

Вход	`ШЕСТЬ.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST BOXES`
Выход	`TEXYDST.E.IXIXIXXSSMPPS.B..ESEUSFXDIIOIIIT` ^[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. Выходные данные

^ БАНАН |

^ БАНАН | | ^ БАНАНА | ^ БАНАНNA | ^ БАНААНА | ^ БАНNANA | ^ BAАНАНА | ^ BБАНАН | ^

A NANA | ^ B A NA | ^ БАН А | ^ BANAN B Анана | ^ N ANA | ^ BA N A | ^ BANA ^ BANANA | | ^ БАНАН

АНАНА | ^ B
ANA | ^ BA N
A | ^ BANA N
BANANA | ^
НАНА | ^ B A
NA | ^ БАН А
^ БАНАН | | ^ БАНАН А

BNN ^ AA | А

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

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

функция inverseBWT ( строка s) создать пустую таблицу длина повтора раз // первая вставка создает первый столбец вставить s как столбец таблицы перед первым столбцом таблицы сортировать строки таблицы по алфавиту return (строка, которая заканчивается символом 'EOF')

Объяснение [ править ]

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

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

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

Обратное преобразование
Вход
BNN ^ AA \| А
Добавить 1	Сортировка 1	Добавить 2	Сортировка 2
BNN^АА\|А	АААBNN^\|	BANANA^ BANAN\| ^А \|	ANANА \|BANANA^ B\| ^
Добавить 3	Сортировка 3	Добавить 4	Сортировка 4
ЗАПРЕТNANNA \|^ BAАНААНА\| ^ BА \| ^	АНААНАА \| ^ЗАПРЕТNANNA \|^ BA\| ^ B	БАНАNANANA \| ^^ БАНАНАНАНА \| \| ^ BAА \| ^ B	АНАНАНА \| А \| ^ BБАНАNANANA \| ^^ БАН\| ^ BA
Добавить 5	Сортировка 5	Добавить 6	Сортировка 6
БАНАНNANA \| NA \| ^ B^ БАНААНАНААНА \| ^ \| ^ БАНА \| ^ BA	АНАНААНА \| ^А \| ^ BAБАНАНNANA \| NA \| ^ B^ БАНА\| ^ БАН	БАНАНNANA \| ^NA \| ^ BA^ БАНАНАНАНА \| АНА \| ^ B \| ^ БАНАА \| ^ БАН	АНАНА \| АНА \| ^ BА \| ^ БАНБАНАНNANA \| ^NA \| ^ BA^ БАНАН\| ^ БАНА
Добавить 7	Сортировка 7	Добавить 8	Сортировка 8
БАНАН \| NANA \| ^ BNA \| ^ БАН^ БАНАНАНАНА \| ^АНА \| ^ BA \| ^ БАНАНА \| ^ БАНА	АНАНА \| ^АНА \| ^ BAА \| ^ БАНАБАНАН \| NANA \| ^ BNA \| ^ БАН^ БАНАН\| ^ БАНАН	БАНАН \| ^NANA \| ^ BANA \| ^ БАНА^ БАНАН \| АНАНА \| ^ BАНА \| ^ БАН \| ^ БАНАНА \| ^ БАНАН	АНАНА \| ^ BАНА \| ^ БАНА \| ^ БАНАНБАНАН \| ^NANA \| ^ BANA \| ^ БАНА^ БАНАН \| \| ^ БАНАН
Выход
^ БАНАН \|

Оптимизация [ править ]

Ряд оптимизаций может сделать эти алгоритмы более эффективными без изменения вывода. Нет необходимости представлять таблицу ни в кодировщике, ни в декодере. В кодировщике каждая строка таблицы может быть представлена одним указателем на строки, и сортировка выполняется с использованием индексов. Необходимо проявлять некоторую осторожность, чтобы гарантировать, что сортировка не будет демонстрировать плохое поведение в худшем случае : стандартные библиотечные функции сортировки вряд ли будут подходящими. ^{[ требуется разъяснение ]}В декодере также нет необходимости хранить таблицу, да и сортировка вообще не нужна. Во времени, пропорциональном размеру алфавита и длине строки, декодированная строка может генерироваться по одному символу справа налево. «Символ» в алгоритме может быть байтом, битом или любым другим удобным размером.

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

${\ displaystyle BWT [i] = {\ begin {case} T [SA [i] -1], & {\ text {if}} SA [i]> 0 \\\ $, & {\ text {иначе} } \ end {case}}}$ ^[3]

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

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

Биективный вариант [ править ]

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

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

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

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

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

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

Вход

Все
вращения

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

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

Выход

^ БАНАН |

^ ^^^^^^^ ... (^) B BBBBBBB ... (B) АНАН АНАН ... (АН) НАНА НАНА ... (НД) АНАН АНАН ... (АН) НАНА НАНА .. . (NA) A AAAAAAA ... (A)

A AAAAAAA ... (A) A NANANAN ... (AN) A NANANAN ... (AN) B BBBBBBB ... (B) N ANANANA ... (NA) N ANANANA ... (NA) ^ ^ ^^^^^^ ... (^)

AAAAAAA ... ( )А Н АНАНАН ... (А Н )А Н АНАНАН ... (А Н ) Б BBBBBBB ... ( B )Н А НАНАНА ... (Н А )N A NANANA ... (N A ) ^ ^^^^^^^ ... ( ^ )

ANNBAA ^ |

Обратное биективное преобразование
Вход
ANNBAA ^
Добавить 1	Сортировка 1	Добавить 2	Сортировка 2
АNNBАА^	АААBNN^	AANANABBANAN^^	AAANANBBNANA^^
Добавить 3	Сортировка 3	Добавить 4	Сортировка 4
AAANANNANBBBАНААНА^^^	AAAАНААНАBBBNANNAN^^^	AAAANANANANABBBBАНАНАНАН^^^^	AAAAАНАНАНАНBBBBNANANANA^^^^
Выход
^ БАНАН

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

^ БАНАН

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

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

Вход	`ШЕСТЬ.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST BOXES`
Слова Линдона	`S IX .MIXED.PIXIES.SIFT.SIXTY.PIXIE .DUST .BOXES`
Выход	`STEYDST.E.IXXIIXXSMPPXS.B..EE..SUSFXDIOIIIIT`

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

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

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

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

Пример реализации [ править ]

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

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

def  bwt ( s :  str )  ->  str :  "" "Применить преобразование Барроуза – Уиллера к входной строке." ""  assert  " \ 002 "  не  в  s,  а  " \ 003 "  не  в  s ,  "Входная строка не может содержать STX и Символы ETX "  s  =  " \ 002 "  +  s  +  " \ 003 "  # Добавить начало и конец  таблицы  текстовых маркеров =  sorted ( s [ i :]  + s [: i ]  for  i  in  range ( len ( s )))  # Таблица поворотов строки  last_column  =  [ row [ - 1 :]  для  строки  в  таблице ]  # Последние символы каждой строки  возвращают  "" . join ( last_column )  # Преобразовать список символов в строку

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

def  ibwt ( r :  str )  ->  str :  "" "Применить обратное преобразование Барроуза – Уиллера." ""  table  =  [ "" ]  *  len ( r )  # Сделать пустую таблицу  для  i  в  диапазоне ( len ( r )):  table  =  sorted ( r [ i ]  +  table [ i ]  для  i  в  диапазоне ( len ( r ))) # Добавить столбец r  s  =  [ строка  для  строки  в  таблице  if  row . endwith ( " \ 003 " )] [ 0 ]  # Найти правильную строку (заканчивающуюся на ETX)  return  s . rstrip ( " \ 003 " ) . strip ( " \ 002 " )  # Избавляемся от маркеров начала и конца

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

BWT в биоинформатике [ править ]

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

Ссылки [ править ]

^ a b Берроуз, Майкл ; Уиллер, Дэвид Дж. (1994), Алгоритм сжатия данных без потерь с блочной сортировкой , Технический отчет 124, Digital Equipment Corporation
^ "Адриен-Могенет / Scala-BWT" . GitHub . Проверено 19 апреля 2018 года .
^ Симпсон, Джаред Т .; Дурбин, Ричард (15.06.2010). «Эффективное построение графа сборочной строки с использованием FM-индекса» . Биоинформатика . 26 (12): i367 – i373. DOI : 10.1093 / биоинформатики / btq217 . ISSN 1367-4803 . PMC 2881401 . PMID 20529929 .
^ a b Манзини, Джованни (1999-08-18). «Преобразование Барроуза-Уиллера: теория и практика» (PDF) . Математические основы компьютерных наук 1999: 24-й международный симпозиум, MFCS'99 Szklarska Poreba, Польша, 6-10 сентября 1999 г., Материалы конференции . Springer Science & Business Media. ISBN 9783540664086.
^ Gil, J .; Скотт, Д.А. (2009 г.), Преобразование сортировки двухъективных строк (PDF)
^ Kufleitner, Manfred (2009), "О биективных вариантами Burrows-Wheeler преобразующих", в Голуба, Ян; Жарек Ян (ред.), Пражская конференция по струнологии , стр. 65–69, arXiv : 0908.0239 , Bibcode : 2009arXiv0908.0239K.
^ * Lothaire, M. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, 17 , Perrin, D .; Reutenauer, C .; Berstel, J .; Пин, JE; Pirillo, G .; Foata, D .; Сакарович, Дж .; Саймон, I .; Шютценбергер, депутат; Choffrut, C .; Cori, R .; Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.), Cambridge University Press , стр. 67, ISBN 978-0-521-59924-5, Zbl 0874,20040
^ Дюваль, Жан-Пьер (1983), «Факторизация слов по упорядоченному алфавиту», Журнал алгоритмов , 4 (4): 363–381, DOI : 10.1016 / 0196-6774 (83) 90017-2 , ISSN 0196-6774 , Zbl 0532,68061 .
^ Salson М, Lecroq Т, Леонар М, Mouchard л (2009). «Четырехэтапный алгоритм обновления преобразования Барроуза-Уиллера». Теоретическая информатика . 410 (43): 4350–4359. DOI : 10.1016 / j.tcs.2009.07.016 .
^ Ли Р; и другие. (2008). «SOAP: короткая программа выравнивания олигонуклеотидов» . Биоинформатика . 24 (5): 713–714. DOI : 10.1093 / биоинформатики / btn025 . PMID 18227114 .
Перейти ↑ Li H, Ruan J, Durbin R (2008-08-19). «Картирование коротких последовательностей ДНК читает и вызывает варианты с использованием показателей качества картирования» . Геномные исследования . 18 (11): 1851–1858. DOI : 10.1101 / gr.078212.108 . PMC 2577856 . PMID 18714091 .
^ Langmead B, C Trapnell, Pop M, Salzberg SL (2009). «Сверхбыстрое и эффективное с точки зрения памяти выравнивание коротких последовательностей ДНК с геномом человека» . Геномная биология . 10 (3): R25. DOI : 10.1186 / GB-2009-10-3-r25 . PMC 2690996 . PMID 19261174 .
Перейти ↑ Li H, Durbin R (2009). «Быстрое и точное согласование короткого чтения с помощью преобразования Барроуза – Уиллера» . Биоинформатика . 25 (14): 1754–1760. DOI : 10.1093 / биоинформатики / btp324 . PMC 2705234 . PMID 19451168 .
^ Ли Р; и другие. (2009). «SOAP2: улучшенный сверхбыстрый инструмент для согласования краткого чтения» . Биоинформатика . 25 (15): 1966–1967. DOI : 10.1093 / биоинформатики / btp336 . PMID 19497933 .

Внешние ссылки [ править ]

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

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

[2] "Адриен-Могенет / Scala-BWT" . GitHub . Проверено 19 апреля 2018 года .

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

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

[5] Gil, J .; Скотт, Д.А. (2009 г.), Преобразование сортировки двухъективных строк (PDF)

[6] Kufleitner, Manfred (2009), "О биективных вариантами Burrows-Wheeler преобразующих", в Голуба, Ян; Жарек Ян (ред.), Пражская конференция по струнологии , стр. 65–69, arXiv : 0908.0239 , Bibcode : 2009arXiv0908.0239K.

[7] * Lothaire, M. (1997), Комбинаторика слов , Энциклопедия математики и ее приложений, 17 , Perrin, D .; Reutenauer, C .; Berstel, J .; Пин, JE; Pirillo, G .; Foata, D .; Сакарович, Дж .; Саймон, I .; Шютценбергер, депутат; Choffrut, C .; Cori, R .; Линдон, Роджер; Рота, Джан-Карло. Предисловие Роджера Линдона (2-е изд.), Cambridge University Press , стр. 67, ISBN 978-0-521-59924-5, Zbl 0874,20040

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

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

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

[Li,_H2008-11] Перейти ↑ Li H, Ruan J, Durbin R (2008-08-19). «Картирование коротких последовательностей ДНК читает и вызывает варианты с использованием показателей качества картирования» . Геномные исследования . 18 (11): 1851–1858. DOI : 10.1101 / gr.078212.108 . PMC 2577856 . PMID 18714091 .

[Langmead2009-12] Langmead B, C Trapnell, Pop M, Salzberg SL (2009). «Сверхбыстрое и эффективное с точки зрения памяти выравнивание коротких последовательностей ДНК с геномом человека» . Геномная биология . 10 (3): R25. DOI : 10.1186 / GB-2009-10-3-r25 . PMC 2690996 . PMID 19261174 .

[Li,_H2009-13] Перейти ↑ Li H, Durbin R (2009). «Быстрое и точное согласование короткого чтения с помощью преобразования Барроуза – Уиллера» . Биоинформатика . 25 (14): 1754–1760. DOI : 10.1093 / биоинформатики / btp324 . PMC 2705234 . PMID 19451168 .

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

[1]