다음의 예제는 Clustering기법을 최근 주목받는 DnaMicroArray 실험해석에 적용한 예이다. 이러한 SubsetsOfBioinformatics 외에도 많은 분야에서 사용되고 있슴을 상기하기 바란다.

실험 : 시간별 대장균 유전자 발현패턴을 알기 위해 DnaMicroArray실험. 대장균 시료를 2분간격으로 샘플링하여 총 16개의 유전자를 올려놓은 칩에 놓고 분석한다.

• 여기서 실제 DNA chip에는 보통 6000개의 유전자가 올려지며, 예제에 사용된 대장균은 DoublingTime이 20분이므로 cell cycle에 관한 시간별 10개의 데이타가 얻어질 것이다.

위 실험을 통해 얻을 수 있는 데이타는 각 유전자의 발현정량정도(수치데이타). 따라서 다음과 같은 matrix를 얻을 수 있다.

• 2분 4분 6분 8분 10분 12분 14분 16분 18분 20분

• gene1 gene2 gene3 gene4
• .... gene16

위(10 * 16) matrix를 가지고 실제 시간대별 발현양상이 비슷한 유전자끼리 Clustering할 수 있다.

Average linkage method(UPGMA)는 각각의 유전자를 순서에 상관없는 모든 조합에 대해 pair하고 이들 사이의 EuclideanDistance를 구한다. 그리고 가장 작은 쌍을 골라낸뒤, 그값의 평균을 취하고 그 두값을 버린 후 위의 과정을 반복한다.

yong27은 위 과정을 파이썬으로 프로그래밍해보았습니다. 물론 초보가 짠거라 말그대로 허접이지만, 오픈소스의 장점을 살려... 여기서 진화하는 코드가 되었스면 좋겠네요. TreeView까지 해서 Dendrogram까지 그림이미지로 좌악 보여주었으면 좋겠는데, 만만치가 않아서... 지금 PIL 모듈로 노가다하는 중입니다. (이것도 좀 쉽게 할수 있는 방법이 없을까요?)

현재 코드는 Clustering된 후의 마지막 Tree구조를 튜플형식(a,(b,c))으로 프린트해주고 각 연결노드간의 Distance를 사전형식으로 프린트합니다.

소스 Cluster.py

Cluster.py를 만드는데 있어서, Python사전에서 각 value들이 실수값들일때 가장 작은 실수값을 갖는 key,value쌍찾기가 넘 오래걸린다. 현재로선

   1 def minValInDict(aDict): 
   2     minVal=1000000; minKey='' 
   3     for key,value in aDict.iteritems(): 
   4         if value < minVal: 
   5             minVal=value; minKey=key 
   6     return minKey, minVal 

이 가장 빨리 계산하나, 그래도 늦는건 마찬가지다. 어떤 방법이 필요할까 하다가 PythonKoreaUserGroup에 질문. Perky씨가 대답해주었다. 새로운 것들을 많이 배우네... FibonacciHeap, HeapQueueAlgorithm등등...

물론 다른계산들이 포함되있긴 하나. 기존의 사전(아이템 6만개)으로 44초걸렸던걸, FibHeap써서 37초... 아직 좀 갈길이 멀다. 문제는 다른곳에???

• 일단 위의 루프를 reduce로만 대신해도 속도가 좀 빨라질 겁니다. 그리고 FibHeap이나 heapq 등을 쓰면 retrieval 시간은 거의 걸리지 않습니다. O(1)이죠. 추가를 해나갈 때 이미 sorting이 되는 셈이거든요. 만약 최소값만이 제일 중요하다면, 아싸리 아이템이 추가될 때마다 항상 최소값만 계산해 갖고 있게 바꿀 수 있습니다. 추상화를 해서 하나의 클래스(dictionary의 서브클래스 등)로 만들어 쓰면 좋겠죠. 그리고 Psyco를 한번 써보세요. 평균적으로 2배 이상 속도 향상을 봅니다(특히 이경우는 5배 이상의 속도향상을 보지 않을까 생각합니다). 또 다른 방법으로는, aDict를 (value,key)의 리스트로 바꾼다음 min 함수를 적용하는 방법이 있습니다. --김창준

  • 그렇군요. 감사합니다. 일단, 최소값을 갖고있게 하는건 제외해야할 것 같습니다. 최소값의 아이템을 지워야하거든요. 그렇다면, 속도향상을 위해서는 다음의 방법들로 요약할 수 있겠군요.
    • 루프를 reduce로

    • FibHeap, heapq : 현재 Cluster.py에 쓰고 있습니다.

    • Psyco : 생소합니다. 찾아봐야겠네요
    • 사전을 리스트로 변경후 min함수적용 : 이것도 매 iteration에 쓰기엔 좀 오래걸릴듯 합니다만... 함 해봐야죠

--yong27, 2003-02-11

PIL 모듈을 다운받아서 써 봤는데 재밌네요. 생각보다 느리지도 않고.. destine, 2003-01-23