본문 바로가기

Bioinformatics/Algorithms34

BWT(Burrows Wheeler transform)의 후-전 특성 버로우즈 휠러 변형의 LF 특성은 이전에 언급한 BCR 알고리즘을 이해하기 위해서 매우 중요하다. 본인도 이를 알지 못한 상태에서 코드와 논문을 이해하다 보니 뭔가 빠진 듯한 느낌이 들었는데.. 이제야 알게 되어서 이를 정리해둔다. 이 내용은 http://www.homolog.us/Tutorials/index.php?p=2.7&s=6에서 가져왔다. 후-전(LF) 특성왜 BWT가 유용한가?만약 매우 긴 서열을 변환한다면, BWT는 유사한 문자들을 모이게 하고, 더 압축을 할 수 있도록 해준다. 예를 들어, 변형된 서열에서, 두개의 'o'가 가 같이 오고, 세번째 o도 가까이에 있게 된다.BWT의 두번째 특성은 염기 검색 수행에 유용하다. 이것은 후-전 사상(LF mapping)이라고 불린다. 그것을 설명하.. 2014. 9. 17.
memcpy 성능 평가 본 글은 http://mail-index.netbsd.org/tech-perform/2002/10/16/0000.html 에서 가지고 왔다. Subject: Performance of various memcpy()'s To: None From: Bang Jun-Young List: tech-perform Date: 10/16/2002 04:18:30 --mYCpIKhGyMATD0i+ Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Hi, About 14 monthes ago, I had some discussion on memcpy performance on i386 platform here. Monthes later, I t.. 2014. 9. 11.
메모리 룩업 테이블 구성(cache) 가장 빠른 방식은 배열이다. 이 방식은 요소의 갯수가 적을 때 유용하다. 다만, 이 배열 방식은 키에 해당 하는 값의 상한 값 만큼의 메모리를 요구한다. uint64_t look_up[64]; 상한 값이 큰 경우에는 해시맵을 이용할 수 있다. 키와 값 쌍을 선언하면 된다.hash_map look_up; 다른 방법으로는 pair의 배열이나 벡터를 생성하고 이를 정렬한 후에 이진 검색하는 방법이 있다. #include #include #include #include #include const int N = 16000; typedef std::pair CALC; CALC calc[N]; static inline bool cmp_calcs(const CALC &c1, const CALC &c2) { return.. 2014. 9. 5.
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.