Review of Algorithms

과제 2, 문자열 조작 - 역방향 보수

DNA 서열의 역방향 보체 서열을 반환하는 파이썬 코드를 작성하십시오. 예를 들어, "ACCTGG"의 역 보수 시퀀스는 "CCAGGT"입니다. 코드는 입력 파일을 명령줄 인수로 사용하고, 입력 파일에서 DNA 서열을 읽고, DNA 서열을 반전하고, DNA 서열의 모든 'A', 'T', 'C', 'G'를 각각 'T', 'A', 'G's, 'C'로 변환하고, 출력 파일에 역방향 보수 서열을 인쇄해야 합니다. 입력 파일이 한 줄의 주석으로 시작하고 두 번째 줄의 DNA 서열이 여러 줄이라고 가정합니다.

주의

LearnUs를 통해 파이썬 코드를 제출하십시오. 파일 이름을 "Assignment2.py"로 지정합니다.

메모

입력 시퀀스는 대/소문자를 구분하지 않습니다. 입력 파일에 DNA 서열이 없으면 "DNA 서열 없음"을 인쇄하십시오. DNA 서열의 역방향 보체 서열을 반환이란 ACCTGG => 꺼꾸로 읽기 => A>T, T>A, C>G, G>C로 변환 후 출력 input파일을 끝까지 전부 읽은 후(줄바꿈이나 띄어쓰기는 무시) 반전을 시킨다. 딕셔너리나 빌트인 함수 써도 ㄱㅊ

 

Deterministic Finite Automaton (DFA)

결정적 유한 오토마타

- DFA는 각 상태에서의 입력에 대해 정확히 하나의 전이를 가지며, 전이는 결정론적입니다.

a, b 는 항상 char형식 not string

1. 상태 집합 Q: 자동 기계의 모든 가능한 상태를 나타냅니다.
2. 알파벳 Σ: 입력 신호의 유한한 집합으로, 자동 기계가 처리할 수 있는 문자를 나타냅니다.
3. 전이 함수 δ: Q × Σ → Q로 정의되며, 현재 상태와 입력 문자를 다음 상태로 매핑하는 규칙입니다.
4. 시작 상태 q₀: 자동 기계가 처음 시작하는 상태입니다. q₀ ∈ Q.
5. 종료 상태(들) F: 입력 문자열을 처리한 후 자동 기계가 수용할 수 있는 최종 상태의 집합입니다. F ⊆ Q.

ex)

- Binary strings of length-2 (0,1 인 DFA 제작)

- Strings of ‘a’ and ‘b’ that include “aa” at least once

- Strings of ‘a’ and ‘b’ that do not have “aa”

 

Constructing automaton [a|b]* a b

- DNA sequences starting with “TA” and ending with “AA”

 

- DNA sequences that include at least one ‘G’

 

DNA sequences that do not have “AA”

 

퀴즈?(한번 생각 해 보기?)

DNA sequences that start with "TA" but do not have "AA"