Bioinformatics/Algorithms34 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. 서열 데이터로부터 분산 k-mer 빈도 세는 방법 FASTQ의 경우 quality 부분과 read identifier를 제외한 순수한 서열만을 남겨둔다.가령 uncorrected.fq -> uncorrected.read, uncorrected.qualFASTA의 경우 read identifier를 제외한 순수한 서열만을 남겨둔다.가령 uncorrected.fa -> uncorrected.read 위의 conversion을 수행하는 과정에서 max_read_length (가장 긴 read 길이)와 size_of_sequences (전체 서열의 길이) 저장한다.대략적으로 64비트 머신에서 한 k-mer가 2 bit 인코딩 되었다고 가정하면 (한 read 당 리드 길이 - k-mer 크기 + 1) * 64 만큼씩 처리해야할 k-mer의 정보양이 증가한다. 대.. 2014. 7. 31. 이전 1 2 3 4 5 6 ··· 9 다음
