'Biological Science/Bioinformatics'에 해당되는 글 23건

  1. 2012.05.14 Viterbi algorithm (비터비 알고리즘)
  2. 2012.05.10 Dynamic Programming (동적 프로그래밍) 1
  3. 2012.02.17 Bioinformatics 생물정보학 이란 9
반응형

비터비 알고리즘은 데이터와 모델 (주로 Hidden Markov Model)이 주어졌을때에 가장 확률적으로 높은 상태를 알아내는 방법입니다.

 

동적 프로그래밍 (Dynamic Programming)으로 구현할 수 있고요.

현재의 상태는 그 바로 이전의 상태에의해서만 영향을 받는다는 가정하에 동작합니다.

 

자세한 알고리즘은

Initialization (i = 0):

      v0(0) = 1, vk(0) = 0 for k > 0;

Recursion (i = 1…L):

      vl(i) = el(xi)maxk(vk(i-1)akl);

      ptri(l) = argmaxk(vk(i-1)akl);

Termination:

      P(x, π*) = maxk(vk(L)ak0);

      π*L = argmax­k(vk(L)ak0);

Traceback (i = L…1):

      πi-1 = ptr(πi*)

 

728x90
반응형
Posted by Gun들지마
반응형

Dynamic Programming (동적 프로그래밍)

Dynamic Program은 복잡한 문제를 간단한 하위 문제로 나누어서 푸는 방법입니다.

겹치는 여러가지 문제들을 조금 간단한 문제들로 나누어서 푸는 방법이라 원래의 해결책보다 더욱 적은 시간이 드는 방법입니다. 동적 프로그래밍의 배경은 간단한데요. 한 문제의 다른 부분들을 각자 해결하여서 그 합이 전체의 문제 해결을 이루는 방법입니다. 이러한 각자해결하는 작은 문제들은 주로 같은 문제의 반복들이 많이 있는데, 그러한 반복을 한번만 수행함으로써 계산의 횟수를 줄일 수가 있습니다. 한번 수행한 해결은 다음에 똑같은 문제가 나왔을 때에 저장이 되어서 간편히 불러들이기만 하면되죠.

예를 들어서 피보나치 수열을 찾는데에 다섯번째 수열을 찾는다면

1.     fib(5)

2.     fib(4) + fib(3)

3.     fib(3) + fib(2) + fib(2) + fib(1)

4.     fib(2) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1)

5.     fib(1) + fib(0) + fib(1) + fib(1) + fib(0) + fib(1) + fib(0) + fib(1)

이런식으로 나누어 지게 되는데요. 여기서 fib(2)는 세번 반복되므로 일단 처음 나왔을때 저장을 하여서 다시 나올때에 불러들이기만하면 컴퓨터의 연산을 줄일 수 있는 방법입니다.

 

이러한 Dynamic Programming은 물론 전반적인 프로그래밍 기법에서 많이 쓰이기도 하지만, 특히 Bioinformatics의 프로그래밍에 많이 나오는 개념이고 자료의 크기가 큰 경우에는 거의 대부분 쓰여지니 잘 알아두는게 좋겠네요.

728x90
반응형
Posted by Gun들지마
반응형
한국에 계시는 분들에게 제가 Bioinformatics를 전공한다고 하니, 많은 분들이 생소해 하시더군요.
그게 뭐야? 하시길래 아, 한국말로 생명정보학이에요 라고 했더니, 다시찾아보니 한국에서는 생물정보학이라는 단어를 쓰더군요.

그래도 그게 뭐야 하시는 분들에게는 Biology + Computer Programming입니다 라고 대답해드린답니다.
말그대로, 컴퓨터 프로그래밍을 해서 생물학에서 나온 정보를 처리하거나 분석하는 학문입니다.

컴퓨터 프로그래밍에대한 지식 뿐만 아니라 미생물학이나 분자생물학에대한 배경지식이 있으신 분들이 많이들 하시죠.
이 분야 자체가 최근에 나온 분야라 미국 사람들도 모르는 사람들이 많고, 각 학교에서도 프로그램이 많이 정립되지 않은 학교가 많은데요.
저는 다행히도 학부과정에 Bioinformatics가 있는 몇안되는 학교를 나와서 지금은 더 공부를 하고 있답니다.

컴퓨터가 발달하고 생명공학이 더 발달함에따라 종전에 없던 수많은 정보들이 나오게 되었습니다.
한 예로 인간 게놈 프로젝트 아시죠? 인간의 DNA 유전자 지도를 만들고 그걸 지도화하는 프로젝트인데, 예전에는 이 sequencing이 비용도 어마어마하고 아주 오래걸리는 일이었지만, 새로운 과학기술의 발달로 요즘은 갈수록 비용도 저렴해지고 하루 반나절만에 결과가 나온답니다.

그림: DNA를 1Mbp 시퀀싱하는데 드는 비용입니다.
출처: Wetterstrand KA. DNA Sequencing Costs: Data from the NHGRI Large-Scale Genome Sequencing Program Available at: www.genome.gov/sequencingcosts. Accessed Feb. 16th, 2012

위에 보시다시피 가격도 아주 저렴해져서 이제는 사설 업체에서 200불이면 자기 DNA유전자 지도를 만들어 준다고도 하네요.

이렇게 저렴하고 빨라진 기술때문에 생물학계는 전에없는 자료들의 양으로 넘치게 되는데요.
이런 자료만 있으면 뭐합니까? 이 자료들을 정리하고 이용해먹는 사람이 필요하겠죠?
이때 저희 Bioinformatician들이 들어오는거죠.
이런 방대한 양의 자료들을 분석하는 소프트웨어들을 만들고 데이터베이스화하는데 필수적인 역할을 한답니다.

저희 분야에서 가장 기본적으로 쓰이는 프로그래밍 언어는 Perl입니다. 배우기 쉽고, 생물학쪽의 라이브러리가 잘 되어있으며 텍스트를 다루는데 효과적인 언어이지요.

그리고 C혹은 C++도 많이 쓰는데, 아마 그 이유는 컴퓨터프로그래밍에서 이쪽으로 들어오신 선구자 분들이 가장 자주 다루는 언어여서가 아닐까 하네요.

간혹 자바나 파이썬 같은 언어를 쓰시는 분들도 있고, 자료구조등을 잘 다루기 위해서 직접 Darwin같은 언어를 개발해서 쓰기도 한답니다.

한국에서보면 컴퓨터 프로그래머들은 포화상태라고 볼 수 있는데요. 하지만 이 생명정보학 쪽은 아직까지 한국에서 생소한 분야라 앞으로 전망이 있을 것....같네요...(개인적인 바램이기도 하구요 ㅋ)

뭐 여기 미국도 상황은 비슷합니다. 닷컴 버블이 빠지고 예전에는 졸업만 하면 마이크로 소프트 같은데서 연봉 1억씩주고 모셔갔는데 이제는 워낙 뛰어나지 않으면 컴퓨터 프로그래머로 좋은 직장을 구하기가 예전 같지 않죠.
하지만 Bioinformatician들은 아직까지 많이 활성화가 되어있지않은 반면에 그들이 가진 기술을 요구하는곳은 많이 있는편이라 보통 교수보다 연봉이 쎈 경우도 있더군요.

만약에 컴퓨터 프로그래밍에 관심이 있으시거나 생명공학쪽에 관심이 있으신 분들은 이런 전공도 있구나 하고 알아보시는것도 괜찮을것 같네요.

그리고 혹시 궁금한점 있으시면 남겨주시면 제가 성심성의껏 답해드리도록 하겠습니다.
728x90
반응형
Posted by Gun들지마