버로우즈휠러 변환

Burrows–
버로우즈
학급무손실 압축 전처리
data 구조스트링
최악의 경우 성능O(n)
최악의 경우 공간의 복잡성O(n)

버로우스 가족휠러 변환(BWT, 블록 정렬 압축이라고도 함)은 문자열을 유사한 문자의 실행으로 정렬합니다.이는 반복된 문자가 있는 문자열을 전면 이동 변환 및 런타임 부호화 등의 기술로 쉽게 압축할 수 있기 때문에 압축에 도움이 됩니다.더 중요한 것은 첫 번째 원래 문자의 위치 이외의 추가 데이터를 저장할 필요 없이 변환이 가역적이라는 것입니다.따라서 BWT는 텍스트 압축 알고리즘의 효율성을 향상시키는 "자유" 방식이며, 약간의 추가 계산만 필요로 합니다.버로우스 가족휠러 변환은 bzip2와 같은 데이터 압축 기법과 함께 사용할 데이터를 준비하는 데 사용되는 알고리즘입니다.그것은 1994년 마이클 버로우스와 데이비드 휠러가 캘리포니아 팔로 알토의 DEC 시스템 연구 센터에서 일하고 있을 때 발명했다.1983년에 Wheeler가 발견한 미공개 변환에 기초하고 있습니다.알고리즘은 접미사 배열을 사용하여 효율적으로 구현할 수 있으므로 선형 시간 [1]복잡도에 도달합니다.

묘사

문자열이 BWT에 의해 변환되면 변환에 따라 문자의 순서가 바뀝니다.원래 문자열에 자주 발생하는 여러 개의 하위 문자열이 있는 경우 변환된 문자열에는 한 문자가 연속적으로 여러 번 반복되는 여러 장소가 있습니다.

예를 들어 다음과 같습니다.

입력 SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
산출량 TEXYDST.E.IXIXIXXSSMPPS.B..E.S.EUSFXDIIOIIIT[2]

출력은 반복된 문자가 많기 때문에 압축하기가 더 쉽습니다.이 예에서는 변환된 문자열에 동일한 문자의 6개의 실행이 포함되어 있습니다.XX,SS,PP,..,II,그리고.III44글자 중 13글자가 됩니다.

예

변환은 사전순으로 텍스트의 모든 원형 이동을 정렬하고 정렬된 순열 세트에서 원본 문자열의 마지막 열과 색인을 추출함으로써 수행됩니다.S.

입력 문자열 지정S = ^BANANA (아래 표의 1단계), N회(단계 2) 회전합니다.N = 8의 길이입니다.S기호도 고려한 문자열^문자열의 시작과 'EOF' 포인터를 나타내는 빨간색 문자를 나타냅니다. 이러한 회전 또는 원형 이동은 사전 편찬 방식으로 정렬됩니다(3단계).인코딩 단계의 출력이 마지막 열입니다.L = BNN^AA A스텝 3 이후 및 인덱스(0 베이스)I원래의 문자열을 포함하는 행의S이 경우,I = 7.

변혁
1. 입력 2. 모든 것
회전		 3. 분류하다
어휘 순서		 4. 을 선택해주세요.
라스트 컬럼		 5. 출력
^바나나
 
^바나나 ^바나나 ^바나나 ^바나나 ^바나나 ^바나나 ^BA아나 ^B바나나 ^
 
아나나 ^BANA ^BANA ^바나나 ^BANA ^바나나 ^바나나
 
아나나 ^B ANA ^BAN A ^바나N 바나나^ 나나 ^BA NA ^반A ^바나나   ^바난A 
BNN^AA A

다음의 의사 코드를 사용하면, BWT 와 그 역수를 간단하게 계산할 수 있습니다(비효율적이지만).입력 문자열은s에는 마지막 문자인 특수 문자 'EOF'가 포함되어 있으며 텍스트의 다른 곳에서도 나타나지 않습니다. 

BWT(문자열 s) 함수는 테이블을 만듭니다.여기서 행은 모두 알파벳 순으로 반환되는 정렬 행의 가능한 회전입니다(테이블의 마지막 열).
함수 역BWT(문자열 s) create empt table repeat length(s) times // 테이블 정렬 행의 첫 번째 열이 알파벳 순으로 반환되기 전에 첫 번째 열 삽입을 테이블의 열로 만듭니다('EOF' 문자로 끝나는 행).

설명.

이렇게 하면 더 쉽게 압축할 수 있는 데이터가 생성되는 이유를 이해하려면 "the"라는 단어를 자주 포함하는 긴 영어 텍스트를 변환해 보십시오.이 텍스트의 회전을 정렬하면 "he"로 시작하는 회전이 그룹화되며, 이 회전의 마지막 문자(이 문자도 "he" 앞의 문자)는 보통 "t"가 되기 때문에 변환 결과에는 몇 개의 "t" 문자가 포함되어 있을 수 있습니다.din. 따라서 이 변환의 성공 여부는 시퀀스 전에 발생할 가능성이 높은 하나의 값에 따라 결정되므로 일반적으로 적절한 데이터(텍스트 등)의 상당히 긴 샘플(최소 몇 킬로바이트)이 필요합니다.

BWT에서 주목할 만한 점은 BWT가 보다 쉽게 인코딩된 출력을 생성하는 것이 아니라 일반 정렬이 이를 역순으로 수행하므로 원본 문서를 마지막 열 데이터에서 다시 생성할 수 있다는 것입니다.

그 반대는 이렇게 이해될 수 있다.BWT 알고리즘의 마지막 표를 가져와 마지막 열을 제외한 모든 열을 지웁니다.이 정보만 있으면 첫 번째 열을 쉽게 재구성할 수 있습니다.마지막 열은 텍스트의 모든 문자를 나타내므로 첫 번째 열을 얻으려면 이러한 문자를 알파벳 순으로 정렬하십시오.그런 다음 (각 행의) 마지막 열과 첫 번째 열은 문서의 모든 연속된 문자 쌍을 제공합니다. 여기서 마지막과 첫 번째 문자가 쌍을 이루도록 쌍이 주기적으로 지정됩니다.쌍 목록을 정렬하면 첫 번째 열과 두 번째 열이 표시됩니다.이 방법으로 전체 목록을 재구성할 수 있습니다.그런 다음 마지막에 "파일 끝" 문자가 있는 행이 원본 텍스트입니다.위의 예를 반대로 하면 다음과 같이 됩니다.

역변환
입력
BNN^AA A
1을 추가 소트 1 2를 더하기 소트 2
B N N ^ A A
 
A A A B N ^
 
BA NA ^B AN ^ A
 
AN A NA NA ^B ^
3을 더하다 소트 3 4를 더하기 소트 4
반난나 ^BA ANA ^B A ^
 
ANA A ^ 반난나 ^BA ^B
 
바나나나 ^반아난아나 ^BA A ^B
 
AANAN A ^B 바나 나 ^반 ^BA
5를 더하기 소트 5 6을 더하다 소트 6
BANAN NA NA ^B ^BANA 아나 ^BANA A ^BA
 
아나나나 ^A ^BA BANANA NA ^B ^BANA ^BANA
 
바나나 나나 ^NA ^BA ^바나 아나 ^B ^바나 A ^반
 
아나나나 ^B A ^반바나나 ^NA ^BA ^바나
7을 추가 분류 7 8을 더하다 정렬 8
바나나 나나 ^B NA ^반 ^바나나아나 ^아나 ^아나 ^BA ^바나A ^바나
 
아나나 ^ANA ^BA A ^바나나나 ^B NA ^바나나 ^바나나 ^BANANANA
 
바나나 ^나나 ^BA NA ^바나나 ^바나아나 ^BANA ^바나나A ^바나나A
 
아나나 ^BANA ^BANA ^바나나 ^BANA ^바나나 ^바나나
산출량
^바나나

최적화

많은 최적화를 통해 출력을 변경하지 않고 이러한 알고리즘을 보다 효율적으로 실행할 수 있습니다.인코더 또는 디코더에 테이블을 표시할 필요는 없습니다.인코더에서는 테이블의 각 행은 문자열에 대한 단일 포인터로 나타낼 수 있으며 인덱스를 사용하여 정렬할 수 있다.디코더에서는, 테이블을 격납할 필요도 없고, 실제로는 정렬할 필요도 없습니다.알파벳 크기 및 문자열 길이에 비례하는 시간에 따라 복호화 문자열을 오른쪽에서 왼쪽으로 한 글자씩 생성해도 된다.알고리즘의 "문자"는 바이트, 비트 또는 기타 편리한 크기일 수 있습니다.

또한 수학적으로 부호화 문자열은 접미사 배열의 단순한 수정으로 계산될 수 있고 접미사 배열은 선형 시간과 메모리에 의해 계산될 수 있다는 것을 관찰할 수 있다.BWT는 텍스트 T의 서픽스 배열 SA와 관련하여 (1 베이스 인덱싱)으로 정의할 수 있습니다.

[3]

실제 'EOF' 문자는 필요하지 않습니다.대신 'EOF'가 존재하는 경우 문자열의 위치를 기억하는 포인터를 사용할 수 있습니다.이 방법에서는 BWT 출력에 변환된 문자열과 포인터의 최종값이 모두 포함되어야 합니다.그런 다음 역변환에서는 원래 크기로 축소됩니다. 즉, 문자열과 포인터가 지정되고 문자열만 반환됩니다.

알고리즘에 대한 자세한 설명은 Burrows and Wheeler의 논문 또는 여러 온라인 [1]소스에서 찾을 수 있습니다.알고리즘은 EOF의 사용 여부와 정렬의 방향에 따라 다소 다릅니다.사실 원래 제제에서는 EOF [4]마커를 사용하지 않았습니다.

바이젝티브 변종

입력 문자열의 회전은 동일한 변환 문자열로 이어지기 때문에 입력 끝에 EOF 마커를 추가하거나 이와 동등한 작업을 수행하지 않으면 BWT를 반전시킬 수 없습니다.이것에 의해, 입력 문자열과 그 모든 회전을 구별할 수 있습니다.(EOF 문자를 추가하여) 알파벳 크기를 늘리면 이후 압축 단계가 어색해집니다.

변환된 문자열이 원본을 고유하게 식별하는 바이젝티브 버전이 있습니다.이것에 의해, 2개의 문자열은 길이가 같고,[5][6] 문자 순서가 다릅니다.

바이젝티브 변환은 입력을 린든 단어의 증가하지 않는 시퀀스로 인수분해함으로써 계산된다. 그러한 인수분해는 존재하고 Chen-Fox-Lyndon [7]정리에 의해 고유하며 선형 [8]시간 내에 찾을 수 있다.이 알고리즘은 모든 단어의 회전을 정렬합니다. 버로우즈처럼요.휠러 변환. 이렇게 하면 정렬된 n개의 문자열이 생성됩니다.변환된 문자열은 이 정렬된 목록에서 각 문자열의 마지막 문자를 선택하여 가져옵니다.여기서 주의할 점은 길이가 다른 문자열은 일반적인 방법으로 정렬되지 않는다는 것입니다.두 문자열은 영원히 반복되며 무한 반복이 정렬됩니다.예를 들어 "OROOR..."은 "OROOR..."보다 앞에 있으므로 "ORO"는 "OR"보다 앞에 있습니다.

예를 들어 텍스트 "^BANANA"는 원래 문자열에서 이러한 단계(빨간색 문자는 EOF 포인터를 나타냄)를 통해 "ANNBAA"로 변환됩니다.EOF 문자는 바이젝티브 변환에서는 불필요하기 때문에 변환 중에 폐기되어 파일 내의 적절한 위치에 다시 추가됩니다.

문자열이 Lyndon 단어로 분할되어 있으므로 위의 비교 방법을 사용하여 시퀀스 내의 단어가 감소합니다.('^'은 후속 문자로 정렬됩니다.)「^BANANANA」는 (^) (B) (AN) (AN) (A)가 된다.

바이젝티브 변환
입력 모든.
회전		 알파벳 순으로 정렬됨 마지막 열
회전된 린든어의		 산출량
^바나나
 
^^^^^^^^... (^) BBBBB... (B)ANANANANANANAN... (NA)ANANANANAN... (NA)ANANANANANANANA... (A)AAAAAA... (A)
 
AAAAAA...(A)아나난...(AN)아나난...(AN)나나난...(B)나난...(NA)나난...(^)나난...
 
AAAAAA...(A)아나난...(AN)아나난...(AN)나나난...(B)나난...(NA)나난...(^)나난...
 
AnnBAA^
역분사 변환
입력
AnnBAA^
1을 추가 소트 1 2를 더하기 소트 2
A N N B A ^
 
A A A B N ^
 
AA NA BB AN ^^
 
AA AN BB NA NA ^^
3을 더하다 소트 3 4를 더하기 소트 4
AAA NAN NABB ANA ^^^
 
AAA ANA BBB NAN ^^^
 
AAAA NANA NANA BBB ANAN ANAN ^^^^
 
AAAA ANAN ANAN BBB NANA ^^^^
산출량
^바나나

마지막 단계까지 프로세스는 역 버로우스와 동일합니다.휠러 프로세스. 그러나 여기서는 반드시 단일 시퀀스의 회전을 제공하는 것이 아니라 대신 Lyndon 워드의 회전을 제공합니다(프로세스가 계속 진행됨에 따라 반복되기 시작합니다).여기에서는 (A), (AN) (2회), (B), (^)의 4개의 다른 단어를 볼 수 있습니다. (NANA...는 ANAN의 순환이기 때문에 다른 단어를 나타내지 않습니다.) 이때 이들 단어는 (^), (B), (AN), (AN), (A)의 역순으로 정렬됩니다.그런 다음 연결해서

^바나나

버로우스 가족휠러 변환은 실제로 이 바이젝티브 변환의 특별한 경우로 볼 수 있습니다.문자열의 끝을 나타내기 위해 알파벳 외부에서 새로운 문자를 도입하는 대신 문자열의 선두에 있는 기존의 모든 기존 문자를 비교하는 새로운 문자를 도입할 수 있습니다.스트링 전체가 Lyndon 워드가 되어 버렸습니다.따라서 그것을 bijectionive process를 통해 실행하면 변환된 결과가 나타나 Lyndon 워드를 반전시켰을 때 마지막에 다시 조립할 필요가 없습니다.

따라서 변환된 텍스트는 Lyndon 워드당 1글자씩 BWT 결과와 다릅니다.예를 들어 입력을 6글자로 분해하면 출력은 6글자만 다릅니다.예를 들어, 이젝티브 변환을 적용하면 다음과 같은 이점이 있습니다.

입력 SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
린든어 SIX.MIXED.PIXIES.SIFT.SIXTY.PIXIE.DUST.BOXES
산출량 STEYDST.E.IXXIIXXSMPPXS.B..EE..SUSFXDIOIIIIT

바이젝티브 변환에는 동일한 문자의 실행이 8개 포함됩니다.다음 순서는 다음과 같습니다.XX,II,XX,PP,..,EE,..,그리고.IIII.

이러한 실행에는 총 18자가 사용됩니다.

다이나믹 버로우즈 -휠러 변환

텍스트를 편집할 때 해당 텍스트의 버로우스는 다음과 같습니다.휠러 변환이 변경됩니다.Salson [9]등은 Burrows를 추론하는 알고리즘을 제안한다.원본 텍스트에서 편집된 텍스트를 휠러 변환하여 원본 Burrows에서 제한된 수의 로컬 재정렬을 수행합니다.휠러 변환, 버로우즈 건설보다 빠를 수 있습니다.편집된 텍스트를 직접 휠러 변환합니다.

구현 예시

이 Python 구현은 단순성을 위해 속도를 희생합니다. 프로그램은 짧지만 실제 구현에서 요구되는 선형 시간보다 더 오래 걸립니다.기본적으로 의사 코드 섹션의 기능을 수행합니다.

STX/ETX 제어 코드를 사용하여 텍스트의 시작과 끝을 표시하고s[i:] + s[:i]을 구축하다i제1회전sforward 트랜스폼은 정렬된 각 행의 마지막 문자를 사용합니다.

방어하다 부하(s: 스트레이트) -> 스트레이트:     "버로우스를 적용하세요.휠러에서 입력 문자열로 변환합니다."""     주장하다 "\002" 것은 아니다. 에 s 그리고. "\003" 것은 아니다. 에 s, "입력 문자열에는 STX 및 ETX 문자를 포함할 수 없습니다."     s = "\002" + s + "\003"  # 텍스트 마커 시작 및 끝 추가     테이블 = 정렬했다(s[i:] + s[:i] 위해서 i 에 범위(렌(s)))  # 끈의 회전표     last_column = [배를 젓다[-1:] 위해서 배를 젓다 에 테이블]  # 각 행의 마지막 문자     돌아가다 "".합류하다(last_column)  # 문자 목록을 문자열로 변환

역변환은 반복하여 삽입한다.r표의 왼쪽 열로 표시하고 표를 정렬합니다.전체 테이블이 작성되면 ETX로 끝나는 행에서 STX 및 ETX를 뺀 행을 반환합니다. 

방어하다 Ibwt(r: 스트레이트) -> 스트레이트:     "역 버로우스를 적용하십시오.휠러 트랜스폼"""     테이블 = [""] * 렌(r)  # 빈 테이블 만들기     위해서 i 에 범위(렌(r)):         테이블 = 정렬했다(r[i] + 테이블[i] 위해서 i 에 범위(렌(r)))  # r 열을 추가합니다.     s = [배를 젓다 위해서 배를 젓다 에 테이블 한다면 배를 젓다.으로 끝나다("\003")][0]  # 올바른 행 찾기 (ETX로 끝)     돌아가다 s.스트립("\003").벗다("\002")  # 시작 및 종료 마커 제거

Manzini의 구현 노트에 이어 간단한 null 문자 접미사를 대신 사용하는 것과 같습니다.정렬은 총체 촬영 순서(오른쪽에서 왼쪽으로 읽힌 문자열)로 수행해야 합니다.sorted(..., key=lambda s: s[::-1])([4]위의 제어 코드는 실제로는 마지막 문자인 EOF를 만족시키지 못합니다.두 개의 코드가 실제로는 첫 번째 코드입니다.그래도 로테이션은 유지됩니다.)

BWT 어플리케이션

무손실 압축 알고리즘으로서 버로우스는Wheeler Transform은 인코딩이 가역적이기 때문에 원래 데이터를 압축에서 복구할 수 있다는 중요한 품질을 제공합니다.Burrows 알고리즘의 무손실 품질은 다양한 목적을 염두에 둔 다양한 알고리즘을 제공합니다.예를 들어, Burrows Wheeler Transform은 시퀀스 얼라인먼트, 이미지 압축, 데이터 압축 등의 알고리즘에 사용됩니다.다음은 Burrows에 주어진 몇 가지 용도를 정리한 것입니다.휠러 트랜스폼

시퀀스 정렬용 BWT

2000년대 말 차세대 시퀀싱(NGS) 기법의 등장으로 Burrows의 또 다른 응용이 이루어졌습니다.휠러 트랜스포메이션NGS에서 DNA는 작은 조각으로 조각나며, 처음 몇 개의 염기가 배열되어 각각 30에서 500개의 염기쌍("DNA 문자") 길이의 수백만 개의 "판독"을 생성한다.예를 들어 ChIP-Seq의 많은 실험에서, 이제 과제는 이러한 판독치를 기준 게놈에 맞추는 것이다. 즉, 해당 유기체의 알려진 거의 완전한 염기서열(최대 수십억 개의 염기쌍 길이일 수 있음)에 맞추는 것이다.이 작업에 특화된 다수의 정렬 프로그램이 발표되었으며, 처음에는 해시에 의존했다(예: Eland, [10]SOAP 또는 Maq[11]).시퀀스 정렬에 대한 메모리 요건을 줄이기 위해 Burrows를 사용하는 여러 정렬 프로그램[14](Bowtie,[12] BWA [13]및 SOAP2)이 개발되었습니다.휠러 트랜스폼

이미지 압축용 BWT

버로우스 가족Wheeler Transformation(휠러 변환)은 이미지 압축 애플리케이션의 기본인 것으로 입증되었습니다.예를 들어, Burrows의 적용을 기반으로 한 압축 파이프라인 표시 -반전, 런렝스 및 산술 인코더에 이은 휠러 변환.이 경우 개발된 파이프라인은 버로우스로 알려져 있다.반전 인코더(BWIC)를 사용한 휠러 트랜스폼.BWIC에 의해 나타난 결과는 Lossless_J와 같이 널리 사용되는 잘 알려진 알고리즘의 압축 성능을 능가하는 것으로 나타났다.PEG 및 JPEG_2000.BWIC는 Lossless_J보다 성능이 우수합니다.PEG와 JPEG_2000은 방사선 의료 영상의 최종 압축 크기를 각각 5.1%와 4.1%로 계산했다.개선사항은 BWIC와 사전 B를 조합하여 달성됩니다.수직 스네이크 오더 방식으로 이미지를 WIC 스캔합니다.보다 최근에는 의 작업과 같은 추가 작업이 Burrows의 구현을 보여주고 있습니다.휠러 변환은 알려진 MTF(Move-to-Front Transform)와 함께 이미지를 거의 무손실 압축합니다.

Genomic 데이터베이스 압축용 BWT

콕스 등은 인간 게놈 정보를 포함한 여러 게놈 데이터셋의 첫 번째 압축 단계 동안 적용된 알고리즘으로 BWT를 사용하는 게놈 압축 체계를 제시했다.그들의 연구는 BWT 압축이 두 개 이상의 접두사 문자의 접미사가 같을 수 있다는 사실을 이용하는 이전과 동일한 부호화("SAP")라고 불리는 두 번째 단계 압축 메커니즘을 포함함으로써 강화될 수 있다는 것을 제안했다.Cox 등은 압축 메커니즘 BWT-SAP를 사용하여 게놈 데이터베이스 ERA015743, 135.5GB 크기에서 압축 체계 BWT-SAP가 ERA015743 데이터 세트를 약 94%(8.2GB) 압축한다는 것을 보여주었다.

시퀀스 예측을 위한 BWT

BWT는 또한 기계 학습과 자연 언어 처리의 공통 연구 영역인 시퀀스 예측에도 유용한 것으로 입증되었다.특히 Ktistakis 등은 버로우스의 무손실 압축을 활용하는 SuBSeq라는 시퀀스 예측 체계를 제안했다.휠러 트랜스폼SuBSeq는 FM 인덱스를 추출한 후 backwardSearch, forwardSearch, neighborExpansion 및 getConcequents라는 일련의 작업을 수행하여 서픽스가 지정된 예측을 검색합니다.예측은 가중치에 따라 분류되며, 가중치가 가장 높은 요소가 SuBSeq 알고리즘의 예측으로 주어지는 배열에 배치됩니다.SuBSeq는 훈련 시간과 정확성 측면에서 시퀀스 예측을 위한 최첨단 알고리즘의 성능을 능가하는 것으로 나타났다.

레퍼런스

  1. ^ a b Burrows, Michael; Wheeler, David J. (1994), A block sorting lossless data compression algorithm, Technical Report 124, Digital Equipment Corporation
  2. ^ "adrien-mogenet/scala-bwt". GitHub. Retrieved 19 April 2018.
  3. ^ Simpson, Jared T.; Durbin, Richard (2010-06-15). "Efficient construction of an assembly string graph using the FM-index". Bioinformatics. 26 (12): i367–i373. doi:10.1093/bioinformatics/btq217. ISSN 1367-4803. PMC 2881401. PMID 20529929.
  4. ^ a b Manzini, Giovanni (1999-08-18). "The Burrows–Wheeler Transform: Theory and Practice" (PDF). Mathematical Foundations of Computer Science 1999: 24th International Symposium, MFCS'99 Szklarska Poreba, Poland, September 6-10, 1999 Proceedings. Springer Science & Business Media. ISBN 9783540664086.
  5. ^ Gil, J.; Scott, D. A. (2009), A bijective string sorting transform (PDF)
  6. ^ 를 클릭합니다Kufleitner, Manfred (2009), "On bijective variants of the Burrows–Wheeler transform", in Holub, Jan; Žďárek, Jan (eds.), Prague Stringology Conference, pp. 65–69, arXiv:0908.0239, Bibcode:2009arXiv0908.0239K.
  7. ^ *Lothaire, M.(1997년), 단어, 백과 사전 수학의 적용에 Combinatorics, vol. 17일 페랭, D;Reutenauer, C;Berstel, J., 핀, J.E.;피릴로, G;Foata, D;Sakarovitch, J., 사이먼, 나;Schützenberger, M.P.;Choffrut, C;코리, R.Lyndon, 로저, 로타, Gian-Carlo.추천 서문 로저 린든(2판)에 의해 캠브리지 대학 출판소 페이지의 주 67, 아이 에스비엔 978-0-521-59924-5, Zbl 0874.20040.
  8. ^ 를 클릭합니다Duval, Jean-Pierre (1983), "Factorizing words over an ordered alphabet", Journal of Algorithms, 4 (4): 363–381, doi:10.1016/0196-6774(83)90017-2, ISSN 0196-6774, Zbl 0532.68061.
  9. ^ Salson M, Lecroq T, Léonard M, Mouchard L (2009). "A Four-Stage Algorithm for Updating a Burrows–Wheeler Transform". Theoretical Computer Science. 410 (43): 4350–4359. doi:10.1016/j.tcs.2009.07.016.
  10. ^ Li R; et al. (2008). "SOAP: short oligonucleotide alignment program". Bioinformatics. 24 (5): 713–714. doi:10.1093/bioinformatics/btn025. PMID 18227114.
  11. ^ Li H, Ruan J, Durbin R (2008-08-19). "Mapping short DNA sequencing reads and calling variants using mapping quality scores". Genome Research. 18 (11): 1851–1858. doi:10.1101/gr.078212.108. PMC 2577856. PMID 18714091.
  12. ^ Langmead B, Trapnell C, Pop M, Salzberg SL (2009). "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome". Genome Biology. 10 (3): R25. doi:10.1186/gb-2009-10-3-r25. PMC 2690996. PMID 19261174.
  13. ^ Li H, Durbin R (2009). "Fast and accurate short read alignment with Burrows–Wheeler Transform". Bioinformatics. 25 (14): 1754–1760. doi:10.1093/bioinformatics/btp324. PMC 2705234. PMID 19451168.
  14. ^ Li R; et al. (2009). "SOAP2: an improved ultrafast tool for short read alignment". Bioinformatics. 25 (15): 1966–1967. doi:10.1093/bioinformatics/btp336. PMID 19497933.
  15. ^ Collin P, Arnavut Z, Koc B (2015). "Lossless compression of medical images using Burrows–Wheeler Transformation with Inversion Coder". 2015 37th Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC). Vol. 2015. pp. 2956–2959. doi:10.1109/EMBC.2015.7319012. ISBN 978-1-4244-9271-8. PMID 26736912. S2CID 4460328.
  16. ^ Devadoss CP, Sankaragomathi B (2019). "Near lossless medical image compression using block BWT–MTF and hybrid fractal compression techniques". Cluster Computing. 22: 12929–12937. doi:10.1007/s10586-018-1801-3. S2CID 33687086.
  17. ^ Cox AJ, Bauer MJ, Jakobi T, Rosone G (2012). "Large-scale compression of genomic sequence databases with the Burrows–Wheeler transform". Bioinformatics. Oxford University Press. 28 (11): 1415–1419. arXiv:1205.0192. doi:10.1093/bioinformatics/bts173. PMID 22556365.
  18. ^ Ktistakis R, Fournier-Viger P, Puglisi SJ, Raman R (2019). "Succinct BWT-Based Sequence Prediction". Database and Expert Systems Applications. Lecture Notes in Computer Science. Vol. 11707. pp. 91–101. doi:10.1007/978-3-030-27618-8_7. ISBN 978-3-030-27617-1. S2CID 201058996.

외부 링크