아.. comparative genome assembly가 무엇이냐. 생소한 표현이다 assembly면 de novo assembly지 뭔 comparative냐. 아.. 근데 문득 드는 생각이.. 혹시 이거 mapping 해서 assembly 하는거니까 그걸 comparative genome assembly 라고 하는거 아니야? 음.. 맞는거 같다. 특히나 이 사이트를 보니까 더욱 확실한거 같다. comparative genome assembly 이거 그냥 mapping assembly를 뜻하는 거다. 근데 찾다 보니 이런 논문도 나오더라. 역시나 이 논문도 CBCB에서 나온거다. 이 논문에 완전 정확하게 comparative genome assembly의 정의를 내린다. AMOS 프로젝트에서 나온 program을 소개하는 논문인데 이건 패스하자. 이게 중요한게 아니다.
그리고 또 bipartite graph는 뭐냐? 이건 쉽게 끝날 문제가 아닌듯 보인다.. 일단은 여기를 보자. 인트로다. 그거 다 봤으면 여기를 보자. 이거 다 보고 정리하겠다. (단순 graph theory에 대한 건 여기를 보자)
The marriage Problem and Matchings
결혼이란 문제로 maximum matching problem을 설명하자면 ..
아래 그림과 같이 각각 n 명(여기서는 6명)의 싱글 남녀가 있다고 할 때 점은 남여 개체를 의미하고 선은 상호간의 관심이 있는 상대를 의미한다. 예를 들어 Ann 이라는 여성은 Adam과 Bob에게 관심이 있다. 이 때 match가 됐다는 것(matching)은 각 개체가 오직 한사람의 상대와 이어짐을 의미 한다. 아래 빨간 선이 matching을 의미 한다(물론 다른 경우의 수도 있다). 특히 이때 모든 개체가 빠짐 없이 matching이 되면 이를 perfect matching이라 한다(아래 그림).
그러나 일반적인 문제에서는 위와 같이 perfect matching 이 어려운데 이 때 최대의 match를 끌어내는 것이 maximum matching problem이다.
Hall's Theorem
Hall 이란 사람이 perfect matching 이 되기 위한 조건을 정리 했는데 다음과 같다
Hall's Theorem : 두 클래스 X,Y를 갖는 bipartite graph G=(V,E) 가 주어졌을 때 이 G가 perfect matching이 되기 위해서는 클래스 X의 subset인 S에 대해 |Adj(S)| >= |S|를 만족해야 한다. Adj(S) 란건 S에서 부터 연결된 클래스 Y의 개체를 의미. 다르게 이야기 하면 X의 subset S랑 연결 선이 있는 클래스 Y의 사람 수가 최소한 S의 사람수 이상은 되야 된다는 이야기.
그런데 이건 정리지 뭐 이거 자체가 알고리즘이거나 하진 않다. 그래서 여기서 이야기 하길 Dijkstra's algorithm에서 효과적인 알고리즘은 찾는단다. 단계적으로 matching을 개선해서 결국 optimal solution을 찾는다는 건데.. 어쩌라는 거냐. 다음 예를 보자.
아래와 같은 상황이 있다고 하자. 안타깝게도 Dorothy, Evelyn, Carl, Erik은 짝이 없다. 이거 어떻게 해결할거냐. 일단 Dorothy 부터 보자. Dorothy에서 연결될 수 있는 짝이 Bob이고 그렇게 되면 Bob에 연결된 Ann을 Adam에 match 시켜야 하고 다시 또 Adam에 연결되었던 Beth는 Carl과 연결시킨다. 이렇게 함으로써 기존의 match M에서 새로운 match M' (|M'| = |M| +1) 이 생기게 된다.
여기서 중요한건 alternative path (= a-path)가 있었다는 것. 음 이게 뭐냐면.. unmatch vertex 에서 시작해서 unmatch vertex로의 path. 즉 길. 근데 왜 alternative이냐 이 길에서 홀수 번째 edge는 현재 match M에서 사용되지 않고 있는 edge이고 짝수 번째 edge는 M에 사용되는 edge인데 이 짝수 번째 edge 대신 홀수 번째 edge를 match로 여기면 이게 새로운 match M'가 되기 때문이다.
이것에 대한 pseudo code는 다음과 같다.
여기서 핵심은 3번째 라인 a-path를 찾는것. 여기서는 modified Breadth-First-Search를 언급하나 이건 패스.
마지막에 a-path가 없을때까지 improve를 시켰다면 이것이 과연 optimal maximum match 인가를 증명한다. 이건 생략
The marriage Problem and Matchings
결혼이란 문제로 maximum matching problem을 설명하자면 ..
아래 그림과 같이 각각 n 명(여기서는 6명)의 싱글 남녀가 있다고 할 때 점은 남여 개체를 의미하고 선은 상호간의 관심이 있는 상대를 의미한다. 예를 들어 Ann 이라는 여성은 Adam과 Bob에게 관심이 있다. 이 때 match가 됐다는 것(matching)은 각 개체가 오직 한사람의 상대와 이어짐을 의미 한다. 아래 빨간 선이 matching을 의미 한다(물론 다른 경우의 수도 있다). 특히 이때 모든 개체가 빠짐 없이 matching이 되면 이를 perfect matching이라 한다(아래 그림).
Hall's Theorem
Hall 이란 사람이 perfect matching 이 되기 위한 조건을 정리 했는데 다음과 같다
Hall's Theorem : 두 클래스 X,Y를 갖는 bipartite graph G=(V,E) 가 주어졌을 때 이 G가 perfect matching이 되기 위해서는 클래스 X의 subset인 S에 대해 |Adj(S)| >= |S|를 만족해야 한다. Adj(S) 란건 S에서 부터 연결된 클래스 Y의 개체를 의미. 다르게 이야기 하면 X의 subset S랑 연결 선이 있는 클래스 Y의 사람 수가 최소한 S의 사람수 이상은 되야 된다는 이야기.
그런데 이건 정리지 뭐 이거 자체가 알고리즘이거나 하진 않다. 그래서 여기서 이야기 하길 Dijkstra's algorithm에서 효과적인 알고리즘은 찾는단다. 단계적으로 matching을 개선해서 결국 optimal solution을 찾는다는 건데.. 어쩌라는 거냐. 다음 예를 보자.
아래와 같은 상황이 있다고 하자. 안타깝게도 Dorothy, Evelyn, Carl, Erik은 짝이 없다. 이거 어떻게 해결할거냐. 일단 Dorothy 부터 보자. Dorothy에서 연결될 수 있는 짝이 Bob이고 그렇게 되면 Bob에 연결된 Ann을 Adam에 match 시켜야 하고 다시 또 Adam에 연결되었던 Beth는 Carl과 연결시킨다. 이렇게 함으로써 기존의 match M에서 새로운 match M' (|M'| = |M| +1) 이 생기게 된다.
여기서 중요한건 alternative path (= a-path)가 있었다는 것. 음 이게 뭐냐면.. unmatch vertex 에서 시작해서 unmatch vertex로의 path. 즉 길. 근데 왜 alternative이냐 이 길에서 홀수 번째 edge는 현재 match M에서 사용되지 않고 있는 edge이고 짝수 번째 edge는 M에 사용되는 edge인데 이 짝수 번째 edge 대신 홀수 번째 edge를 match로 여기면 이게 새로운 match M'가 되기 때문이다.
마지막에 a-path가 없을때까지 improve를 시켰다면 이것이 과연 optimal maximum match 인가를 증명한다. 이건 생략
