Bioinformatics/Algorithms34 GenomeMapper 색인 생성 본 문서는 내 동료 Jorg의 diploma thesis의 내용 중 일부를 번역한 것이다. 색인 구조 생성(mkindex) 이 프로그램은 각 지놈 혹은 조합된 지놈에 대해서 오직 한 번만 수행되어야 한다. 이것은 해시 색인을 생성하여 씨드의 발생과 위치의 빠른 룩업을 가능하게 하고, 참조 서열에 대해 계통([생물]strains)의 다른점들과 관련이 있는 모든 서열 정보를 포함하는 시퀀스 그래프를 생성한다. 입력으로 프로그램은 단지 FASTA 포맷으로 된 참조 서열 하나 혹은 다수의 다른 계통 서열들을 받을 수 있다. 각 계통들은 하나의 분리된 입력 파일 안에 있어야 한다. 이 프로그램은 모든 변이에 대해서 염색체, 서열의 위치, 그리고 계통적 다형성(삽입이 삭제와 SNP보다 더 선호된다)에 따라 오름차순.. 2012. 11. 29. 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. 이전 1 ··· 4 5 6 7 8 9 다음
