Pruning Trees지난 글에서 정리했던 브루트포스 & Score 함수를 이용한 motif 탐색 알고리즘은 시간이 매우 오래 걸렸다.이는 각 Score 함수의 실행 시간은 짧았지만 motif 조합을 다 해봐야했기 때문에 Score 함수의 호출 횟수가 너무 많았기 때문이다.하지만 모든 경우에 대해 매번 Score 함수를 호출해야만할까? pruning tree 알고리즘을 사용하여 호출 횟수를 줄여보자.이 알고리즘은 현재까지 발견한 최적해와 비교하여, 현재 하려는 계산이 더 최적이 될 것 같지 않을 때 굳이 계산해보지 않고 과감하게 건너뛰는 방법이다. 예를 들어보자.10개의 DNA에서 공통적으로 등장하는 10-mer motif 를 찾으려고 한다.이때 4개 DNA 에 대해서 점수를 계산했더니 17점이 나왔고..

지난 글에서는 초기 코로나 바이러스의 DNA 패턴을 분석하는 방법으로 k-mers 라는 부분 문자열로 나누어서 분석하는 방법을 알아보았다. 지난 글 마지막에서 보았을 때는, 초기 코로나 바이러스의 스파이크 단백질 염기 서열을 알고 있었고, 그 단백질의 염기서열을 코돈으로 번역하여 아미노산 서열을 찾아보았다. 하지만 실제로는 지난 글과 같이 '염기서열을 알고있는' 상태에서 찾는 것이 아니라, 염기 서열 안에서 유전자를 찾아야 하는 상황이 더 많다.만약 우리가 찾아야 하는 유전자의 염기 서열을 모를 때 유전자를 어떻게 찾을 수 있을까? 우리는 모든 유전자가 특정 코돈 (AUG) 으로 시작하고 특정 코돈들 중 하나 (TAA, TAG, TGA) 로 끝나는 것을 알고있다.그렇다면 개시 코돈과 종결 코돈만으로 유전..

FASTA : 생물학적 서열에 대한 공통 포맷 각 FASTA 문자열은 '>' 로 시작하는 header line 으로 시작한다.그 다음에는 여러 줄의 문자열 데이터가 들어오는데,DNA 는 ACGT 로 구성된 문자열이RNA 는 ACGU 로 구성된 문자열이단백질은 ACDEFGHIKLMNOPQRSTUVWY 로 구성된 문자열이 주어진다. 하나의 문자열은 또 다른 header line 을 만나거나 EOF 신호를 만나면 끝난다.따라서 하나의 FASTA 파일에는 여러 시퀀스가 존재할 수 있다.또한 각 시퀀스는 0-index 가 아니라 1-index 형태를 따른다.  예를 들어 SARS-COV-2Wuhan.fasta 파일을 보면 첫 줄에는 > 로 시작하는 헤더라인이 있다.그 다음줄에는 ATCG 로 구성된 DNA 염기서열..

생물 정보학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 ..

노드 : p2p 네트워크를 구성하는 하나의 소프트웨어 (호스트) 를 말한다. 모든 노드는 동등하다.비트코인의 정신이 탈 중앙화이기 때문에 특정 노드에게 더 권한을 준다거나 하는 것이 없다. p2p 네트워크는 TCP를 기반으로 만들어진다.그리고 이 네트워크에는 새로운 노드가 언제든 참여하고 떠날 수 있다.노드로 참여할 때는 특정 사이트에서 비트코인을 돌리고 싶은 데 내 이웃 노드가 되어달라고 요청하고, 요청이 수락되면 연결을 짓는 식으로 네트워크에 참여하게 된다. (요청 보내는 대상 노드를 가리켜 시드 노드라고 한다.) 노드의 행동각 노드의 행동 방식을 보기에 앞서 앨리스가 밥에게 비트코인을 보내는 트랜잭션을 만들었다고 해보자.그러면 이 트랜잭션은 전체 비트코인 네트워크에 퍼져야만 한다.앨리스는 월렛 프로..

비트코인 스크립트에는 P2PKH 말고도 용도에 따라 다양한 타입의 트랜잭션이 존재할 수 있다.지난 글에서는 P2SH 라는 타입의 트랜잭션을 추가적으로 정리하였다.이번 글에서는 다른 종류의 트랜잭션들에 대해 추가적으로 정리해본다.  Timelock비트코인 input 부분의 sequence, 트랜잭션 자체의 timelock 외에도 스크립트와 관련하여 timelock을 사용할 수도 있다.타임 락은 트랜잭션 자체에서 명시할 수도 있지만, output script 에서도 명시할 수 있다.그러면 그 시간이 지난 시점부터 이 output 에서 비트코인을 꺼낼 수 있도록 하는 것이다.  타임락은 이렇게 트랜잭션 레벨의 타임락과 UTXO 레벨의 타임락으로 구분이 될 수 있다.그래서 사실 input 에 제시되는 seque..

위 그림은 비트코인 output 의 모습을 간단하게 보여준다.이 output 은 2개의 output을 나타내고, 첫번째 output 은 0.015 를 지불하며 이때 output script 는 scriptPubKey 로 위와 같은 문자열이 들어간다. 이 output 이 밥에게 비트코인을 보내는 아웃풋이라면, 밥이 비트코인을 꺼내서 쓸 때는 input script 에 저 output script 의 값이 참이 되도록 하는 값을 제시하도록 한다.위의 빨간색 문자열이 퍼블릭 키 (밥의 비트코인 주소) 를 나타내고, 밥은 이 퍼블릭키에 쌍에 맞는 프라이빗 키로 서명을 제시해서 나중에 비트코인을 꺼낼 수 있다.  인풋을 간단하게 보면 위와 같이 되어있다.위 그림에서는 1개의 인풋만을 보여주고 있으며,output이..

이 그림은 비트코인의 동작을 한 페이지에 정리한 모습을 나타낸다.맨 왼쪽에는 블록체인이 존재한다.제네시스 블록 (높이가 0인 블록) 부터 그 위로 하나씩 블록을 차곡 차곡 쌓으면서 블록 체인이 형성된다.비트코인을 사용한 거래가 발생하여 그에 대한 트랜잭션이 발생하면, 채굴자는 그 트랜잭션을 모아서 블록으로 만들고, 작업 증명에 성공하면 채굴된 블록을 발표한다.만약 이 블록이 다수의 사용자에 의해 받아들여지면 그 블록에 포함된 트랜잭션들은 다수에 의해 인정받는 유효한 트랜잭션이 된다.  비트코인의 트랜잭션은 위와 같이 생겼다.먼저 트랜잭션에는 input, output 부분이 있고, input 에는 비트코인이 빠져나갈 위치가 들어간다.(정확히는 나의 계좌의 최종 잔고를 나타내는 트랜잭션들이 들어간다.)out..

비트코인은 '통신 프로토콜' 이다.사카시 나카모토는 비트코인을 위해 컨센서스, 채굴, 비트코인 생성 방법, 트랜잭션과 같은 내용들을 프로토콜로 만들어 두었고, 비트코인 코어와 같은 소프트웨어가 프로토콜을 실제로 구현한 것과 같다.지금은 비록 사카시 나카모토는 빠졌지만 '비트코인 코어' 는 여전히 권위있는 프로그램이다.그래서 새로운 아이디어가 등장하면 먼저 코어 프로그램에 적용을 하고, 이후에 다른 버전 소프트웨어에도 적용된다. 비트코인 코어와 같은 프로그램을 다운받아서 실행하면, 코인이 생성이 되고, 이 코인을 하나의 어카운트에서 다른 어카운트로 보낼 수 있다.그리고 이 보내는 행위를 '트랜잭션' 이라고 한다.각각의 트랜잭션은 '블록' 에 기록이 되고, 이 블록들이 순서에 따라 연결된 것을 '블록체인' ..

암호학(Cryptology)은 비밀 통신과 관련된 과학 분야를 말한다.암호학은 크게 Cryptography 와 Cryptanalysis 로 분류된다.Cryptography는 암호를 만드는 것과 관련된 분야, Cryptanalysis 는 암호를 깨는 것과 관련된 분야이다.위 3개 개념을 통틀어서 Crypto 라고 부르기도 한다. 물론 암호학을 공부하는 사람은 이 두 분야를 모두 공부해야 한다.자신이 만든 암호화 알고리즘이 얼마나 공격에 강력한지 입증하려면 공격 수단에 대한 이해도 필요하기 때문이다. 암호학 분야가 달성하려는 목표는 4가지가 있다. 1. Confidentiality (기밀성)A가 B에게 메세지를 보낼 때, B 이외에는 아무도 이 메세지의 내용을 알 수 없도록 만드는 것현대에는 Symmetri..