[python, rosalind] Overlab Graphs

Rosalind를 풀면서 항상 실수를 연발하게 됩니다.  휴우.. 최근들어 다시 Rosalind를 풀기 시작했는데, 멘델의 법칙문제와 이번 포스팅의 주제인 Overlab Graphs를 아주 고전하면서 풀었습니다.

 

먼저 이야기하지만, Rosalind를 풀때는 꼭 깊게 생각하시고, 생각을 다양하게 해보시기 바랍니다. 예를들어 FASTA파일을 읽을 때, >이후로 1줄만 읽게 한다던가................ 한 6번 틀린것 같습니다. 이것 때문에..

 

바보인증샷

제 알고리즘은 맞았습니다. 물론.. 코드가 더럽긴하지만요. 그런데 파스타파일의 특정을 잃어버리고 있었더라구요.

 

아무튼 진행해보도록 하겠습니다.

 

---

 설명은 다음과 같습니다.

1. A Brief Introduction to Graph Thery

 

 네트워크는 어디에서든 있고, 질병이 퍼지는 모델에서 자주 사용이 되긴 하지만, 이 네트워크는 더 광범위하게 사용이 된다고 합니다(요즘 Graph이용해서 deep learning도 하고 있잖습니까..). 그런데 네트워크 하면 떠오르는 것은 뭔가 연결하고 있는 그림을 생각하게 됩니다.

우리가 생각하는 네트워크그림

우리는 이러한 네크워크를 그림없이 어떻게 네트워크를 계산적으로 표시를 할것이냐에 대해서 생각해볼 필요가 있습니다.

 

계산적인 네트워크를 확인하기 위하여 단어를 정의하자면

graph : 네트워크를 기술적으로 말하는 것

nodes(or vertical) : graph를 구성하고 있는 요소중 하나

edges : nodes를 연결해주는 것들

 

만약에 v와 w를 이어주는 edge가 있다면, v,w로 표시된다(혹은 w,v).

 

- v,w의 경우 v,w에 어떠한 일이 생겼다고 가정이 되는 것입니다. 이럴때 우리는 v와 w가 인접해있다(adjacent)라고 이야기 합니다.

- v의 정도(degree)는 edge의 수입니다.

- walk는 한 node의 끝자리가 다음노드의 시작이 되는 edge의 정렬된 모음입니다({v1,v2},{v2,v3},{v3,v4}...).

- path는 대부분 두개의 edges에서 모든 node에 발생하는 walk를 뜻합니다.

  ( 이 부분은 제가 생각하기에는 path는 위의 네트워크 그림을 생각하면 될 것 같습니다.)

- path length는 path에서 edges의 수입니다.

- cycle 은 첫번째 노드가 마지막노드인 path이다(cycle안에서 정확하게 두개의 edges가 모든 node에 있을때, 왔다 갔다 할수있는 경우!)

- 두 vertice(node)사이의 거리(distance)는 그들을 연결하는 최단 거리의 길이이다.

 

2. Problem 

 본격적으로 문제풀이에 나서자면,

 

Sample Dataset이 있는데, FASTA파일을 보여줍니다. 이때, 결과를 보게 되면 앞자리가 같은걸 뽑으면 되나?라는 실수를 할수가 있습니다.

 

그러지 마시고, Problem을 읽어 보시면 앞에(prefix) 3자리, 뒤에(suffix) 3자리가 같을 경우를 가져오면 되는 것입니다.

 

그리고 가장 중요한 것은 FASTA 파일을 줄 때, Sample Dataset으로 주는 것이 아닌것을 아셔야 합니다. FASTA파일의 구조를 잘 알고 계셔야 하는데, >이후로 염기서열이 나오는데, 특정 염기서열수가 넘으면 다음 줄로 넘어가기 때문에 이점을 참고 하시고 진행하세요(저는 이부분 때문에 6번 틀렸습니다.).

 

코드는 굳이 공개 하지 않아도 될것같아 하지 않겠습니다.