다음의 예제는 [[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쌍찾기가 넘 오래걸린다. 현재로선 {{{#!python def minValInDict(aDict): minVal=1000000; minKey='' for key,value in aDict.iteritems(): if value < minVal: minVal=value; minKey=key return minKey, minVal }}} 이 가장 빨리 계산하나, 그래도 늦는건 마찬가지다. 어떤 방법이 필요할까 하다가 PythonKoreaUserGroup에 [[http://www.python.or.kr:8080/python/bbs/readArticlepy?bbsid=bbs&article_id=7569|질문]]. [[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