Bioinformatics61 Lightweight BWT Construction for Very Large String Collection 핵심 부분 이 알고리즘은 대량의 서열 정보로 부터 BWT된 FM-index를 생성할 수 있도록 해주는 알고리즘을 제안한다. 그중 세 저자의 이름을 따서 하나는 BCR (Markus J. Bauer-Anthony J. Cox-Giovanna Rosone), 그것의 확장된 버전은 BCRext라고 부른다. 처음에는 해당 논문의 번역 내용을 올릴려고 했으나, 완전히 이해하고 쉽게 풀어서 설명하는 것이 더 나은 듯 하여 여기에 정리해 둔다. 구현은 BEETL이라는 라이브러리에서 최초 등장했다. BCR 알고리즘 먼저 입력된 서열에 대해 행을 열로 바꾸는(transpose) 연산을 수행한다. 그리고 가장 뒤에 있는 염기에서 부터 한 염기씩 진행해가면서 처리하는데, 이를 횟수라고 하자. 알고리즘은 입력 서열 중 가장 긴 길이의 .. 2014. 8. 15. In-place hybrid Binary-Radix sort 번역 본 내용은 http://www.drdobbs.com/architecture-and-design/algorithm-improvement-through-performanc/220300654의 내용을 번역한 것이다. 기수(radix) 소팅 알고리즘은 배열의 요소들을 서로 비교하지 않기 때문에 비교 기반의 O(nlogn) 성능 제약에 걸리지 않는다. 사실, 그들은 O(kn)의 선형 성능을 가진다. 기수(radix) 정렬은 배열 요소 값의 최상위 숫자(most significant digit, MSD) 혹은 최하위 숫자(least significant digit, LSD) 한 숫자 값만을 취해서 처리한다. 예를 들어, 다음의 두자리 숫자를 정렬하기 하려면 다음과 같이 한다. 각 숫자들을 최상위 숫자값(10의 자리.. 2014. 8. 12. 상수 공간 비교 기반 버로우즈 휠러 변환 원 논문의 제목은 A Constant-Space Comparison-Based Algorithm for Computing the Burrows–Wheeler Transform이다. 원문 내용의 2절의 일부는 다음과 같다. 다음 내용은 0-index 기반이다. 즉, 문자열에서 첫 문자는 index 0을 가진다. 가령, T='temp'에서 T[0] == 't'이고, T[3] == 'p'이다. Given the input text T = T [0 ..n−1] where T [n−1] = $, moving a single character inside T can change the content of many suffixes. The idea to circumvent this difficulty without .. 2014. 8. 7. k-mer로 부터 Bloom Filter (블룸 필터) 생성 k-mer 전체 갯수 * k-mer 당 bit 크기는 bloom filter의 전체 비트 크기가 된다. 블룸 필터는 셋과 마찬가지로 특정 요소가 존재하는지 여부를 판별하는데 사용할 수 있다. 실제 키를 저장하는 것 대신에 키는 비트의 조합으로 변환된다. 그렇기 때문에 메모리 소비양은 줄어들지만, 실제 존재하지 않는 키가 존재하는 것으로 나타나게 될 수 있다. 이를 줄이기 위해서는 해시 함수의 개수를 늘려야 한다. 이는 반드시 다른 종류의 해시 함수를 많이 가질 필요가 있는 게 아니라, 다른 종류의 씨드값을 동일한 해시 함수에 적용함으로써도 얻을 수 있다. k-mer를 읽어들이면서, 해시 함수 갯수만큼 해시 값을 계산하고, 개별 해시 값들에 대해서 블룸 필터 안의 비트 벡터 내에서 인덱스를 구하고, 이 인.. 2014. 8. 2. 이전 1 2 3 4 5 6 7 ··· 16 다음
