11/2일 정리 Network1 : node > MUM,edge > MUM 사이의 공통된 gene(의 수) 로 형성된 네트워크

• 이 네트워크는 서로 완전하게 연결된 5개의 네트워크를 가지고 있다.

• 분석 : minimum spanning tree algorithm을 이용하여 중요하게 생각될 수 있는 node 사이의 상호관계를 제외하고 나머지는 생략하는 network를 만든다.
• 네트워크를 형성 하기 위하여 cytoscape를 사용하였는데 MST를 계산해주는 plugin을 찾아서 적용하기 위하여 시간이 많이 걸렸다. (이번주 내내 했는데 영..)

왜 MST를 해야 하는지 MST로 무엇을 볼수 있는지를 생각 하지 않고 plugin을 사용하니까 이렇게 나오더라 라고 생각 했던 것이 애초 잘못 이다.

• 그래서 현재 cytoscape를 이용하여 만들어진 네트워크를 gml로 export 했고 이 네트워크를 분석할 수 있는 툴을 찾아 보았더니 python을 이용하거나 R을 이용할 수 있었다. R을 사용하기로 했으며 스크립트를 적용 하여 만들어보았다.

• 그리고 노드들 간에 연관관계가 큰 노드들을 연결하여 tree를 만드는 것이 중요하기 때문에 노드들간의 연결된 정도의 역 수로 weight으로 취하여 만들기로 하였다.

( R을 이용하여 할 생각). 그리고 네트워크의 크기가 크기 때문에 랜덤 네트워크(샘플 - 네트워크1과 유사 - 노트 20~30개)를 만든 후 적용 시켜보기로 하였다.

Spanning tree 와 minimum spanning tree 개념

• Spanning tree:어떠한 그래프의 서브그래프이면서 그래프의 모든 노드를 포함하는 트리
• Minimum spanning tree: greed method 의 한 종류 라고 한다.

Greed mothod 는 어떤 결정을 해야 할때 마다 그 순간에 가장 좋다 (최적이다) 라고 생각 되는 것을 선택 함으로써 최종적 해답에 도달 한다.

Minimum spanning tree는 각 노드가 연결된 edge 의 weight에 따라 가장 가까운? 최적의 노드를 선택하여 전체 weight의 합이 가장 낮은 tree를 만든다.

알고리즘으로 prim's algorithm과 Kruskal's algorithm 이 있다.