CS/문제해결기법
6. Advanced Sequence Alignment
Affine Gap 같은 정렬이어도, 왼쪽 것이 더 좋다.어떻게하면 왼쪽처럼 정렬하도록 만들 수 있을까? 여러개 정렬하기한번에 정렬하기 vs 2개씩 정렬하기 메모리 공간 최적화슬라이딩 윈도우분할 정복 ( 심화 내용이라는 느낌이 들어서 정리를 후순위로 미룸 )
전체 글
개발은 좋은데 뭘로 개발할까
CS/문제해결기법
5. Aligning Sequences
지난 글까지는 여러개의 DNA 시퀀스에서 공통 motif (유사한 motif) 를 찾는 방법에 대해 정리하였다.이번 글부터는 지난 글에서 찾아낸 각 DNA 염기 서열 속 motif 들 또는 전체 DNA 염기 서열이 얼마나 유사한지를 확인하기 위해, 정렬하는 방법에 대해 정리한다. 예를 들어, 위 문자열은 사람, 개, 고양이, 돼지의 인슐린 단백질의 아미노산 서열을 나타낸 모습이다.이 서열은 얼마나 유사할까? 유사도를 측정하는 방법 중 하나는 각 문자열을 같은 문자끼리 '정렬' 하는 것이다.위 모습은 4개의 인슐린 단백질 아미노산 염기 서열을 직접 손으로 정렬한 모습을 보여준다.그리고 꽤나 긴 공통 서열이 나타나는 것을 알 수 있다. 그런데 이 공통 서열이 과연 우리가 찾을 수 있는 최적의 서열일까?..
CS/문제해결기법
4. Finding TFBS Motifs in our lifetime
Pruning Trees지난 글에서 정리했던 브루트포스 & Score 함수를 이용한 motif 탐색 알고리즘은 시간이 매우 오래 걸렸다.이는 각 Score 함수의 실행 시간은 짧았지만 motif 조합을 다 해봐야했기 때문에 Score 함수의 호출 횟수가 너무 많았기 때문이다.하지만 모든 경우에 대해 매번 Score 함수를 호출해야만할까? pruning tree 알고리즘을 사용하여 호출 횟수를 줄여보자.이 알고리즘은 현재까지 발견한 최적해와 비교하여, 현재 하려는 계산이 더 최적이 될 것 같지 않을 때 굳이 계산해보지 않고 과감하게 건너뛰는 방법이다. 예를 들어보자.10개의 DNA에서 공통적으로 등장하는 10-mer motif 를 찾으려고 한다.이때 4개 DNA 에 대해서 점수를 계산했더니 17점이 나왔고..
CS/문제해결기법
3. Searching Pattern
지난 글에서는 초기 코로나 바이러스의 DNA 패턴을 분석하는 방법으로 k-mers 라는 부분 문자열로 나누어서 분석하는 방법을 알아보았다. 지난 글 마지막에서 보았을 때는, 초기 코로나 바이러스의 스파이크 단백질 염기 서열을 알고 있었고, 그 단백질의 염기서열을 코돈으로 번역하여 아미노산 서열을 찾아보았다. 하지만 실제로는 지난 글과 같이 '염기서열을 알고있는' 상태에서 찾는 것이 아니라, 염기 서열 안에서 유전자를 찾아야 하는 상황이 더 많다.만약 우리가 찾아야 하는 유전자의 염기 서열을 모를 때 유전자를 어떻게 찾을 수 있을까? 우리는 모든 유전자가 특정 코돈 (AUG) 으로 시작하고 특정 코돈들 중 하나 (TAA, TAG, TGA) 로 끝나는 것을 알고있다.그렇다면 개시 코돈과 종결 코돈만으로 유전..
CS/문제해결기법
2. Genome
FASTA : 생물학적 서열에 대한 공통 포맷 각 FASTA 문자열은 '>' 로 시작하는 header line 으로 시작한다.그 다음에는 여러 줄의 문자열 데이터가 들어오는데,DNA 는 ACGT 로 구성된 문자열이RNA 는 ACGU 로 구성된 문자열이단백질은 ACDEFGHIKLMNOPQRSTUVWY 로 구성된 문자열이 주어진다. 하나의 문자열은 또 다른 header line 을 만나거나 EOF 신호를 만나면 끝난다.따라서 하나의 FASTA 파일에는 여러 시퀀스가 존재할 수 있다.또한 각 시퀀스는 0-index 가 아니라 1-index 형태를 따른다. 예를 들어 SARS-COV-2Wuhan.fasta 파일을 보면 첫 줄에는 > 로 시작하는 헤더라인이 있다.그 다음줄에는 ATCG 로 구성된 DNA 염기서열..
CS/문제해결기법
1. Bioinformatics
생물 정보학information : that which resolves uncertainty. (불확실한 것을 해결하는 방법)컴퓨터 과학에서는 '정보' 를 bit 단위로 표현한다. information = -log₂ (확률) ex1) 동전을 한번 던졌을 때 뒷면이 위에 나타날 확률 = 1/2 → -log₂ (1/2) = 1 (bit)ex2) 2개의 주사위를 던졌을 때 두 수의 합이 7이 될 확률 = 1/6 → -log₂ (1/6) = log₂ 6 = 2.58 (bits)ex3) 2개의 주사위를 던졌을 때 두 수의 합이 3이 될 확률 = 1/18 → -log₂ (1/18) = log₂ 18 = 4.17 (bits) information systems need mechanism for - momory ..
CS/블록체인
[블록체인] 13. Mining
노드 : p2p 네트워크를 구성하는 하나의 소프트웨어 (호스트) 를 말한다. 모든 노드는 동등하다.비트코인의 정신이 탈 중앙화이기 때문에 특정 노드에게 더 권한을 준다거나 하는 것이 없다. p2p 네트워크는 TCP를 기반으로 만들어진다.그리고 이 네트워크에는 새로운 노드가 언제든 참여하고 떠날 수 있다.노드로 참여할 때는 특정 사이트에서 비트코인을 돌리고 싶은 데 내 이웃 노드가 되어달라고 요청하고, 요청이 수락되면 연결을 짓는 식으로 네트워크에 참여하게 된다. (요청 보내는 대상 노드를 가리켜 시드 노드라고 한다.) 노드의 행동각 노드의 행동 방식을 보기에 앞서 앨리스가 밥에게 비트코인을 보내는 트랜잭션을 만들었다고 해보자.그러면 이 트랜잭션은 전체 비트코인 네트워크에 퍼져야만 한다.앨리스는 월렛 프로..
CS/블록체인
[블록체인] 12. 비트코인 script (2)
비트코인 스크립트에는 P2PKH 말고도 용도에 따라 다양한 타입의 트랜잭션이 존재할 수 있다.지난 글에서는 P2SH 라는 타입의 트랜잭션을 추가적으로 정리하였다.이번 글에서는 다른 종류의 트랜잭션들에 대해 추가적으로 정리해본다. Timelock비트코인 input 부분의 sequence, 트랜잭션 자체의 timelock 외에도 스크립트와 관련하여 timelock을 사용할 수도 있다.타임 락은 트랜잭션 자체에서 명시할 수도 있지만, output script 에서도 명시할 수 있다.그러면 그 시간이 지난 시점부터 이 output 에서 비트코인을 꺼낼 수 있도록 하는 것이다. 타임락은 이렇게 트랜잭션 레벨의 타임락과 UTXO 레벨의 타임락으로 구분이 될 수 있다.그래서 사실 input 에 제시되는 seque..
CS/블록체인
[블록체인] 12. 비트코인 script (1)
위 그림은 비트코인 output 의 모습을 간단하게 보여준다.이 output 은 2개의 output을 나타내고, 첫번째 output 은 0.015 를 지불하며 이때 output script 는 scriptPubKey 로 위와 같은 문자열이 들어간다. 이 output 이 밥에게 비트코인을 보내는 아웃풋이라면, 밥이 비트코인을 꺼내서 쓸 때는 input script 에 저 output script 의 값이 참이 되도록 하는 값을 제시하도록 한다.위의 빨간색 문자열이 퍼블릭 키 (밥의 비트코인 주소) 를 나타내고, 밥은 이 퍼블릭키에 쌍에 맞는 프라이빗 키로 서명을 제시해서 나중에 비트코인을 꺼낼 수 있다. 인풋을 간단하게 보면 위와 같이 되어있다.위 그림에서는 1개의 인풋만을 보여주고 있으며,output이..
CS/블록체인
[블록체인] 11. 비트코인 트랜잭션
이 그림은 비트코인의 동작을 한 페이지에 정리한 모습을 나타낸다.맨 왼쪽에는 블록체인이 존재한다.제네시스 블록 (높이가 0인 블록) 부터 그 위로 하나씩 블록을 차곡 차곡 쌓으면서 블록 체인이 형성된다.비트코인을 사용한 거래가 발생하여 그에 대한 트랜잭션이 발생하면, 채굴자는 그 트랜잭션을 모아서 블록으로 만들고, 작업 증명에 성공하면 채굴된 블록을 발표한다.만약 이 블록이 다수의 사용자에 의해 받아들여지면 그 블록에 포함된 트랜잭션들은 다수에 의해 인정받는 유효한 트랜잭션이 된다. 비트코인의 트랜잭션은 위와 같이 생겼다.먼저 트랜잭션에는 input, output 부분이 있고, input 에는 비트코인이 빠져나갈 위치가 들어간다.(정확히는 나의 계좌의 최종 잔고를 나타내는 트랜잭션들이 들어간다.)out..