Bioinformatics61 GenomeMapper 개념 본 내용은 내 동료인 Jorg의 diploma thesis의 일부를 번역한 것이다. 개념 GenomeMapper는 프로그래밍 언어 C를 이용하여 구현되었다. 포인터 연산과 수동 메모리 관리가 이점이며, 다른 프로그래밍 언어에 비해서 실행 시간을 줄여준다. Read란, 예를 들어 fasta 포맷으로 된 염기 서열 데이터 파일을 보면 시퀀싱 머신에서 한 싸이클 당 읽어들인 염기 서열들이 한 줄마다 있게 된다. 즉 이 한 줄에 담긴 염기 서열을 read 라고 부른다. GenomeMapper는 약간씩 다른 지놈들에 있는 수백만의 리드들의 위치를 검출하기 위해 개발되었다. 리드들은 알려지지 않은 지놈으로부터 왔기 때문에, 대부분의 리드들은 원래의 염기 서열에 있어야 하는 영역을 찾지 못할 것이다. 그런 까닭에, .. 2012. 11. 29. Shift-And 문자열 검색 본 문서는 Algorithms on Strings Trees and Sequences의 내용을 일부 번역한 것이다. Shift-And 문자열 검색 R. Baeza-Yates와 G. Gonnet 씨는 상대적으로 짧은 패턴(예를 들어, 전형적인 영어 단어의 길이)의 완전 일치 검색을 매우 효율적으로 해결하는 비트 기반의 방법을 고안하였다. 그들은 이 방법을 Shift-Or 방식이라고 불렀지만, 이것은 Shift-And라고 부르는 것이 더 적절할 것 같다. 패턴 P가 n의 길이를 가지고 있고, 참조 문자열 T가 m의 길이를 가지고 있다고 하자. 정의 M은 (n)X(m+1)의 행렬이고, 행 순서 i는 1부터 n의 길이를 가지고, 열 순서 j는 1부터 m까지라고 하자. 한 요소 M(i, j)는 P의 첫 i번째 문.. 2012. 11. 28. 레벤슈타인 오토마타(Levenshtein Automata) 본 문서는 http://blog.notdot.net/2010/07/Damn-Cool-Algorithms-Levenshtein-Automata을 번역한 것이다. 소개 레벤슈타인 오토마타의 배경에 있는 통찰은 찾으려고하는 단어의 주어진 레벤슈타인 거리 안에 있는 문자열 집합들을 정확히 인지하는 유한 상태 오토마타를 생성하도록 해준다는 것이다. 그리고 어떠한 단어를 제공하던지 간에 오토마타는 생성할 때 명시한 레벤슈타인 거리에 근거하여 찾으려고 하는 단어가 최대 이 거리 안에 있는지 여부를 판단하여 수용하거나 거부할 것이다. 유한 상태 오토마타의 특성 덕분에, 주어진 문자열의 길이에 대해서 시간 안에 처리될 것이다. 시간이 걸리는 표준적인 동적 프로그래밍 레벤슈타인 알고리즘과 비교하여 보자. 여기에서 m과 n.. 2012. 11. 27. 버크하드-켈러 트리(Burkhard-Keller Tree) 본 분서는 http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees의 내용을 번역한 것이다. BK-트리, 또는 버크하드-켈러 트리는 트리 기반의 구조로 주어진 문자열에 대한 빠른 근사 매치를 하도록 해준다. 예를 들어, 스펠링 검사기나 '퍼지(유사어)' 검색을 수행하는 등의 작업에 사용된다. 더 자세히 예를 들자면, "aeek"를 검색하는데 이와 유사한 "seek"과 "peek"의 단어들이 반환되는 것이 목적이다. 무엇이 BK-트리를 빛나게 하냐면, 단순 무식한 무작위 검색 방식(brute-force search) 외에는 뾰족한 검색 방법이 없는 문제가 있을 때, 검색 속도를 엄청나게 향상시킬 수 있는 단순하고 우아한 방법을 제공해 주기 때문.. 2012. 11. 27. 이전 1 ··· 11 12 13 14 15 16 다음
