2023 상반기/바이오 컴퓨팅17 Aho-Corasick(AC)[아호코라식] Algorithm AC 알고리즘은 주어진 텍스트에서 여러 패턴을 동시에 찾는데 사용되는 알고리즘 Process Prefix Tree (Trie) 생성 - 이 단계에서는 주어진 모든 패턴 집합 P에 대한 Prefix Tree (또는 Trie)를 구축합니다. 각 노드는 고유한 문자 라벨을 가지며, 루트에서 특정 노드까지의 경로는 해당 노드에 도달하는 데 사용된 문자열을 나타냅니다. 트리의 모든 노드는 Q에 속하며, 루트 노드는 q0으로 표시됩니다. Accepting States 표시 - 각 패턴 문자열이 Trie에서 끝나는 노드는 "Accepting" 또는 "Output" 상태로 표시됩니다. 이는 해당 노드가 패턴 문자열의 끝을 나타내기 때문입니다. goto 함수 생성 - goto 함수는 주어진 현재 상태와 입력 문자에 .. 2023. 5. 18. multiple sequence alignment & 병합 1. Merge the pairwise alignment into the multiple sequence alignment. PSA의 x MSA의 x 1. not '-' not '-' Align this column 2. not '-' '-' all PSA gap 3. '-' not '-' all MSA gap 4. '-' '-' Align this column PSA PSA0 x YWQLIK y D-EHQH PSA1 x YWQLIK z H--LAK PSA2 x -Y-WQLIK w AAWHL-- MSA x YWQLIK y D-EHQH z H--LAK PSA1 x YWQLIK z H--LAK MSA2 x YWQLIK y D-EHQH z H--LAK PSA2 x -YWQLIK w AAWHL-- MSA3 x .. 2023. 5. 2. Approximate Pattern Matching Approximate Pattern Matching 패천이 정확하게 일치하지 않더라도 유사한 부분 문자열을 찾는 과정 Exhaustive search 적용 방법 여기서 k 는 mismatch를 얼마나 허용할건지에 대한 변수이다. 시간복잡도: O(nm) Dynamic Programming을 적용한 방법 같으면 +0, 다르면 +1 A G C C T T G A T 0 0 0 0 0 0 0 0 0 0 G 0 1 0 1 1 1 1 0 1 1 C 0 1 2 0 1 2 2 2 1 2 A 0 0 2 3 1 2 3 3 2 2 T 0 1 1 3 4 1 2 4 4 2 가장 아래 값이 K이하인 경우 accept 2023. 4. 26. Pattern Matching & Pattern Finding(패턴 매칭) Single Pattern Matching(단일 패턴 매칭): Exhaustive Search: 이 방법은 모든 가능한 위치에서 패턴을 텍스트와 비교하여 일치하는 부분을 찾습니다. 시간 복잡도는 O(nm)입니다(n: 텍스트 길이, m: 패턴 길이). DFA-Based Pattern Matching: Deterministic Finite Automaton(DFA)을 이용하여 패턴을 찾는 알고리즘입니다. 패턴과 일치하는 상태를 통해 문자열을 훑어내려갑니다. 전처리 시간 복잡도는 O(m)이고 검색 시간 복잡도는 O(n)입니다. => O(m) + O(n) KMP Algorithm: Knuth-Morris-Pratt 알고리즘은 전처리를 통해 패턴의 정보를 활용하여 불필요한 비교를 줄입니다. 전처리 시간 복잡도는 .. 2023. 4. 18. Entropy(Hartley, Shannon) & Pattern Matching Progressive Alignment(점진적 정렬) 점진적 정렬 시간복잡도 = k^2 * n 하트리(Hartley)의 공식 : H(X) = log₂(n) 여기서 H(X)는 확률 변수 X의 엔트로피를 나타내며, n은 가능한 결과의 수입니다. 이 공식은 각 결과의 확률이 1/n이고 동일하다는 가정 하에, 이산 확률 변수의 엔트로피를 계산하는 데 사용됩니다. 예를 들어, 동전 던지기의 경우 가능한 결과가 2개(앞면 또는 뒷면)이며, 각 결과의 확률은 동일합니다(1/2). 따라서 하트리의 공식에 따라 동전 던지기의 엔트로피는 log₂(2) = 1입니다. 예시 1: 동전 던지기 동전 던지기는 2개의 결과가 가능하며, 앞면(Head)과 뒷면(Tail)이 각각 1/2의 확률로 발생합니다. H(X) = -(P(Hea.. 2023. 4. 12. 과제 3-1, 3-2 Low Complexity 과제 3-1은 주어진 DNA 시퀀스 파일에서 낮은 복잡도 영역의 시작 위치를 찾아서 출력하고, 각 시퀀스에 소요된 시간을 측정하여 출력해줍니다. 낮은 복잡도 영역은 동일한 DNA 서브 시퀀스가 반복되는 영역입니다. 코드의 주요 부분들은 다음과 같습니다: removeBlank 함수: 문자열에서 공백과 개행 문자를 제거하고, 모든 문자를 대문자로 변환합니다. checkDnaData 함수: 문자열이 올바른 DNA 시퀀스(A, T, G, C로만 구성된 문자열)인지 확인합니다. find_low_complexity 함수: DNA 시퀀스에서 낮은 복잡도 영역의 시작 위치를 찾습니다. 3-1은 정규 표현식을 사용하여 낮은 복잡도 영역을 찾습니다. 3-2는 문자열 인덱싱 및 반복문을 통해 낮은 복잡도 영역을 찾습니다. .. 2023. 4. 6. 이전 1 2 3 다음
