Introduction to graph theory

Theorem 1.1 G가 n개의 vertices를 갖는 multigraph 라고 하면 각 vertex의 degree(vertex에 연결된 edge의 갯수)의 합은 G의 edge 갯수의 2배와 같다.


Corollary 1.2 odd vertices(degree가 홀수인 vertices) 의 갯수는 짝수이다.

• complete graph : graph의 모든 vertices 가 서로 연결되어 있는 graph. Kn 으로 표시. 여기서 n은 order로서 vertices의 수를 의미
• null graph : 그래프 G가 있을때 E(G) =0 인 그래프. 즉 edge가 하나도 없는 그래프. Nn으로 표시. 여기서 n은 vertex 수
• walk : vertex와 edge의 번갈아가면서 나오는 sequence. v0 e0 v1 e1 v2... vn. 이때 길이는 edge의 갯수
• trail : walk 중에 edge가 두개 이상 반복이 안된 walk.
• path : walk 중에 vertex가 두개 이상 반복이 안된 walk. path는 반드시 trail이다. 그러나 역은 반드시 성립하는 것은 아니다.
• distance from x to w : vertex x 에서 vertex w 까지의 최단 path 길이. d(x,w) 로 표현한다.
• closed : vertex u에서 시작해서 vertex v로 끝나는 walk가 있을때 u = v 이면 이는 closed 되어 있다고 한다.
• circuit : closed walk 중에 edge가 반복이 안된 walk.
• cycle : circuit 중에 vertex가 반복이 안된 circuit. Cn 은 n 개의 vertex를 갖는 cycle을 의미
• connected : multigraph G의 모든 vertex가 path로 연결되어 있다면 G는 connected 되었다고 한다.
• isomorphic : 두 그래프 G와 H가 같을때 isomorphic이라 한다. 정확히 이야기 하자면 isomorphism 이라고 불리는 함수 f (그래프 G에서 H로의 mapping(vertex to vertex) 함수로서 그래프 G의 adjacency(두 vertices의 연결)를 유지하게 하는 함수)  가 존재할 때, 두 그래프는 isomorphic 하다라고 한다. isomorphism은 하나 이상이 될 수 있다.
• induced subgraph : H가 G의 induced subgraph 라고 한다면 v(H) 가 v(G)의 subset이고 이 G 안에서 subset 사이에 존재하는 edge가 모두 H에 있음을 의미한다. 

Isomorphism Testing Problem : 두 그래프 G와 H가 isomorphic한가를 판단하는 문제.

--chapter 3--

• bipartite : order(vertex의 갯수)가 최소 2 이상인 그래프 중 vertex가 두 그룹으로 나뉘고 모든 edge가 각 두 그룹의 vertex를 join 하게 할때 이를 bipartite 라고 한다.
• partite sets : bipartite graph에서 두 subgroup(두 vertex set)을 partite set이라 한다.

Theorem 3.1 : 그래프 G는 odd cycle을 포함하지 않을 때(필요충분조건) bipartite 가 된다. 이는 아래 Lemma 3.2를 이용하여 증명할 수 있다.

Lemma 3.2 : odd 길이의 closed walk(시작 vertex와 끝 vertex가 같은 walk)는 항상 odd cycle을 포함한다.

• tree : cycle이 없고 connected 된 graph

Theorem 3.3 : G가 connected graph 라고 할 때, G의 임의의 두 vertex가 unique path에 의해 join 된다면(필요 충분 조건) , G는 tree이다.

Theorem 3.4 : G가 order가 n이고(v(G) = n) size가 m일때(e(G) = m) m = n-1 이면 G는 tree이다.

--chapter 4--

• k-colouring of G : 그래프 G가 있을때 그래프의 각 vertex를 k 개의 색깔로 칠하는 방법. 단 adjacent(연결된 vertex) 한 vertex끼리는 다른색이여야 한다.
• chromatic number of G : k-colouring of G에서 가장 작은 k 값. X(G) 로 표현.

--chapter 6--

• Euler circuit : connected multigraph 인 G가 있을때 G의 모든 edge를 포함하는 circuit.
• Eulerian multigraph : Euler circuit을 갖는 multigraph, 쉽게 이야기 하면 그래프의 모든 edge를 한번씩 통과해서 시작 vertex로 오게 되는 walk를 갖고 있는 graph

Theorem 6.1 G가 connected multigraph 라고 할 때 G의 모든 vertex의 degree가 even 일때(모든 vertex에 연결된 edge의 갯수가 짝수 일때)만 Euler graph이다.

• spanning cycle : order 가 3이상(vertex의 갯수가 3이상)인 그래프 G가 있을 때 모든 vertex를 통과하는 cycle을 spanning cycle 이라 한다. euler circuit과의 차이는 euler circuit는 모든 edge를 포함해야 한다는 것이며 spanning cycle은 모든 vertex를 포함해야 한다는 것이다.
• hamiltonian graph : spanning cycle을 가지고 있는 graph

Rules for constructing Hamiltonian cycles in G

1. degree가 2인 vertex의 모든 edge는 spanning cycle에 포함되어야 한다.

2. spanning cycle을 만드는 도중에 spanning cycle이 아닌 cycle이 형성될 시에는 그 그래프는 Hamiltonian graph가 될 수 없다.

3. spanning cycle을 만드는 도중에 vertex의 2개의 edge가 정해졌다면 그 vertex에 연결된 그 외의 edge는 제거한다.

Theorem 6.3 G가 만약 Hamiltonian graph 라면 V(G)의 non-empty subset S에 의한 c(G-S)는 |S| 보다 작거나 같다. c(G-S) 는 graph G 에서 subset인 S에 포함되는 vertex와 그 vertex에 연결된 edge를 지운 graph 의 component 갯수를 의미. theorem 6.3은 Hamiltonian graph의 필요 조건.

Theorem 6.4 order가 3 이상인 그래프 G가 있을 때, 모든 vertex에 대해 d(v)가 n/2 이상이 되면 이는 Hamiltonian graph 이다.

Theorem 6.5 order가 3 이상인 그래프 G가 있을때 adjacent vertices를 제외한 모든 vertex 페어에 대해서 d(u) + d(v)가 n 보다 크거나 같으면 이는 Hamiltonian graph 이다.

head first design pattern 4

• state pattern : 스테이트 패턴을 이용하면 객체의 내부 상태가 바뀜에 따라서 객체의 행도응ㄹ 바꿀 수 있다. 마치 객체의 클래스가 바뀌는 것과 같은 결과를 얻을 수 있다.
• 예제 : 뽑기 기계가 있다. 뽑기 기계는 4가지 상태(동전 있음, 동전 없음, 알맹이 판매, 알맹이 매진) 가 있고 각 상태를 전환하기 위한 행동(손잡이 돌림, 동전 반환, 동전 투입, 알맹이 내보냄)이 있다. 이를 코딩하라
• 단순 답변 : 각 상태를 나타내는 상수를 정적 변수에 저장한다. 그리고 행동을 메소드로 표현해서 if문을 사용해서 상태에 맞는 각 행동을 취한다. 만약에 10번중에 한번은 특별 당첨으로 2개의 뽑기가 나온다는 기능을 확장하려 한다. 이러면 단순 답변의 코드를 전부 뜯어 고쳐야 한다.
• state pattern : 상태를 나타내는 state 인터페이스를 정의 하고 이를 구현하는 구상 클래스들에서 각 상태에 따른 행동을 정의한다. context는 state를 구성으로 갖고(맴버 변수) 이 상태를 나타내는 맴버 함수에서 state 객체의 메소드를 호출한다.
• proxy pattern : 어떤 객체에 대한 접근을 제어하기 위한 용도로 대리인이나 대변인에 해당하는 객체를 제공하는 패턴
• 예제 : 클라이언트에서 서버에 특정 작업(메소드)를 호출하여 결과값을 받을때

head first design pattern 3

• adapter pattern & facade pattern
• adapter pattern : 한 클래스의 인터페이스를 클라이언트에서 사용하고자 하는 다른 인터페이스로 변환한다. 어댑터를 이용하면 인터페이스 호환성 문제 때문에 같이 쓸 수 없는 클래스들을 연결해서 쓸 수 있다.
• 객체 어댑터 : client 클래스에서는 target 인터페이스를 구성 맴버 변수로 가지고 있고 target 인터페이스를 구현한 구상 클래스인 adapter 클래스가 adaptee를 맴버 변수로 가지고 있어서(구성:composition) client에서 target 변수로 adaptee 객체를 쓸수 있도록 target의 기능에 맞게 adaptee 기능들 wrapping 한다.
• 클래스 어댑터 :  객체 어댑터가 adapter가 adaptee를 구성 맴버로 갖으면서 target 인터페이스를 구현한 것에 반해 클래스 어댑터는 adapter가 target과 adaptee를 다중 상속한다.
• facade pattern : 어떤 서브시스템의 일련의 인터페이스에 대한 통합된 인터페이스를 제공한다. 퍼사드에서 고수준 인터페이스를 정의하기 때문에 서브시스템을 더 쉽게 사용할 수 있다.
• 최소지식원칙을 지키는데 퍼사드 패턴을 사용할 수 있다.
• template method pattern : 템플릿 메소드 페턴에서는 메소드에서 알고리즘의 골격을 정의한다. 알고리즘의 여러 단계 중 일부는 서브클래스에서 구현할 수 있다. 템플릿 메소드를 이용하면 알고리즘의 구조는 그대로 유지하면서 서브클래스에서 특정 단계를 재정의할 수 있다.
• hook : 추상클래스에서 선언되는 매소드이지만 일반적으로 아무 것도 들어 있지 않다. 서브클래스들은 이 후크를 사용해서 특정 순서에 특정 메소드를 시행할 수 있다. 다르게 말하면 추상클래스에서 hook라는 매소드를 만들고 탬플릿 메소드에서 실행시키면 필요 없는 서브 클래스들은 hook에서 null을 return 하면 되고 특정 메소드를 해야 하는 서브클래스에서는 hook 메소드를 오버라이드해서 사용.
• iterator pattern & composite pattern
• iterator pattern : 이터레이터 패턴은 컬렉션 구현 방법을 노출시키지 않으면서도 그 집합체 안에 들어 있는 모든 항목에 접근할 수 있게 해주는 방법을 제공한다.
• 예제 : 두 음식점이 합병됐다. 메뉴판을 합쳐야 하는데 메뉴 클래스는 두 음식점이 통일했다. 하지만 두 음식점이 매뉴들를 담고 있던 컬랙션이 다르기 때문에 웨이트리스라는 객체를 만들었을때 메뉴를 출력하려면 각 컬랙션을 가각 for문을 돌려야 하는 현상이 나타난다.
• 이터레이터 패턴 : iterator 라는 인터페이스를 만들고 각 음식점의 컬랙션에 맞는 구상 iterator 클래스를 만든다. 각 음식점 클래스에서는 이 자신의 메뉴 컬랙션에 맞는 구상 iterator 클래스를 return 한다. 그러면 웨이트리스 객체는 동일한 메소드를 가지고 두 음식의 메뉴 리스트를 출력 가능하다.
• composite pattern : 컴포지트 패턴을 이용하면 객체들을 트리 구조로 구성하여 부분과 전체를 나타내는 계층구조로 만들 수 있다. 이 패턴을 이용하면 클라이언트에서 개별 객체와 다른 객체들로 구성된 복합 객체를 똑같은 방법으로 다룰 수 있다.

디자인 원칙 : 

1. 최소 지식 원칙 : 정말 친한 친구하고만 얘기해라. 아무 객체의 매소드를 호출하는 것이 아니라, 특정 객체(1.객체 자신, 2.메소드에 매개변수로 전달된 객체, 3.그 메소드에서 생성하거나 인스턴스를 만든 객체, 4.그 객체에 속하는 구성요소) 의 메소드만 호출한다.
2. 헐리우드 원칙 : 먼저 연락하지 마라. 우리가 연락하겠다. 이는 고수준 구성요소에서 저수준 구성요소에 하는 소리. 
3. 클래스를 바꾸는 이유는 한 가지 뿐이어야 한다.

head first design pattern 2

• Factory pattern
• Factory method pattern : factory method pattern에서는 객체를 생성하기 위한 인터페이스를 정의하는데, 어떤 클래스의 인스턴스를 만들지는 서브클래스에서 결정하게 만든다. 팩토리 메소드 패턴을 이용하면 클래스의 인스턴스를 만드는 일을 서브클래스에게 맡기는 것이다.
• abstract factory pattern : 추상 팩토리 패턴에서는 인터페이스를 이용하여 서로 연관된, 또는 의존하는 객체를 구상 클래스를 지정하지 않고도 생성할 수 있다.
• factory method pattern은 상송을 통해서 객체를 만들고 abstract factory pattern은 객체 구성(interface의 구현)을 통해서 만든다. 
• 예제 : PizzaStore을 예로 든다. factory method pattern 은 PizzaStore를 추상클래스로 만들어서 이 클래스의 추상 메소드를 derived class 들이 구현하게 한다. abstract factory pattern에서는 PizzaIngrediantFactory 라는 인터페이스를 만들어서 이를 정의 하는 구상 클래스를 만든다.  이때 PizzaStore의 derived class들은 각기 다른 PizzaIngrediantFactory를 맴버변수로 갖고 있어서 이 PizzaIngrediantFactory를 Pizza 객체를 만들때 인자로 넘겨준다. factory method pattern의 PizzaStore에서는 지역별 Pizza 클래스가 있어서 string(예를 들어 "cheese", "clam") 등을 인자로 넘기는데 반해 abstract factory pattern의 경우 지역별 Pizza 클래스가 있는것이 아니라 종류별 Pizza 클래스(예를 들어 "CheesePizza") 가 있어서 PizzaIngrediantFactory 객체를 인자로 넘긴다.
• singleton pattern : 싱클턴 패턴은 해당 클래스의 인스턴스가 하나만 만들어지고, 어디서든지 그 인스턴스에 접근할 수 있도록 하기 위한 패턴이다.
• 필요성 : 스레드 풀, 캐시, 대화상자, 사용자 설정, 레지스트리 설정등을 처리하는 객체는 여러개의 객체가 필요하지 않고 오히려 하나의 객체만 있어야 한다.
• 단순 답변 : 생성자를 private로 하고 생성자를 호출하는 getInstance 라는 static 함수를 만들고 이 함수가 호출 되었을때 private로 되어 있는 생성자를 호출해서 자신의 객체를 만들고 이를 static 맴버 변수에다 넣어서 return 한다.
• 문제점 : 멀티스레드에서 접근할 때 하나 이상의 객체가 생성될 가능성이 여전히 존재
• singleton pattern : 1. getInstance 메소드 자체를 synchromized 키워드를 이용해서 동기화 한다. 혹은 2.static 맴버 변수에다가 프로그램이 시작 하자마자 클래스 객체를 생성해서 집어 넣는다. 혹은 3. DCL(double-checking locking)을 사용한다. 
• command pattern : 커맨드 패턴을 이용하면 요구 사항을 개체로 캡슐화 할 수 있으며, 매개변수를 써서 여러 가지 다른 요구 사항을 집어넣을 수도 있다. 또한 요청 내역을 큐에 저장하거나 로그로 기록할 수도 있으며, 작업취소 기능도 지원 가능하다.
• 예제 : 특정 리모컨이 있는데 여기에는 10개의 슬롯이 있고 각 슬롯에는 on/off 스위치가 두개씩 있다. 그리고 undo 라는 스위치가 하나 있다. 이 리모컨을 만능 리모콘이 되도록 코딩한다. 그러니까 어떤 슬롯은 형광등의 스위치 버튼이 되고 어떤 슬롯은 자동문의 버튼이 되는 것. 문제는 어떤 슬롯이 어떤 일을 할지 모른다는것. 결국 필요한건 메소드의 캡슐화
• command pattern : client는 receiver를 command 객체에 넣어서 이 command 객체를 invoker에게 넘기면 invoker는 command 객체를 실행 시킨다. command 는 interface 이고 execute라는 virtual 함수가 있고 이를 구현한 구상 객체들이 존재한다. 실질적으로 이 구상 객체들이 execute 라는 함수를 구현한다. 이 execute 함수 안에 각 command가 구성 객체로 받는 receiver들의 함수들을 호출하는 것이다. 결국 invoker는 command를 받아서 command 객체의 execute 만 실행 할 뿐 어떤 메소들이 실행되는지는 알 수가 없다. 위 예제를 비유하자면 client는 리모컨을 사용하는 사람이 되겠고 invoker가 리모컨, receiver가 리모컨이 컨트롤 하는 각종 기기들의 function을 정의한 클래스가 되겠고, command는 단지 리모컨의 메소드 캡슐화를 위한 실제적인 receiver 핸들 객체가 되겠다.

head first design pattern 1

head first design pattern에 정의된 내용.

• strategy pattern : strategy pattern 은 알고리즘군을 정의(인터페이스)하고 각각을 캡슐화하여 교환해서 사용할 수 있도록 만든다. 이를 이용하면 알고리즘을 사용하는 클라이언트와는 독립적으로 알고리즘을 변경할 수 있다.
• 예제 : 연못의 오리 게임. Duck 이라는 super class를 만들고 이를 상속 받은 여러 종류의 오리 class가 있다. 원래 Duck class에는 없는 기능을 넣을 려면 어떻게 해야 하는가?
• 단순 답변 : Duck class에 특정 기능의 함수를 넣어준다. 하지만 이는 Duck class를 상속 받은 클래스 모두에게 이 기능이 생기게 된다. 만약 특정 derived class는 이 기능이 변형되어야 한다면?
• strategy pattern : 위 문제는 함수 오버라이딩으로 가능하기는 하지만.. 이보다는 변형 가능한 것들을 하나의 인터페이스로 만든 다음 이것을 Duck class 의 맴버 변수로 넣는다. 구현은 이 인터페이스를 상속받는 여러 클래스들에서 구현. 
• observer pattern : observer pattern 에서는 한 객체(subject)의 상태가 바뀌면 그 객체에 의존하는 다른 객체들한테 연락이 가고 자동으로 내용이 갱신되는 방식으로 일대다 의존성을 정의한다.
• 예제 : 기상스테이션 예제로 WeatherStation이라는 클래스가 있고 이 클래스에서는 기상변화를 관찰 한다. 기상 정보는 실시간으로 WeatherData라는 클래스의 객체로 넘어가고 이때 WeatherData 객체는 이 업데이트된 정보를 각각의 Display 객체들에게 통보해야 한다. 
• observer pattern : Subject 라는 인터페이스를 만들고 그 안에는 Observer 라는 interface를 갖고 있다. WeatherData 클래스는 Subject 인터페이스를 구현하고 있다. Observer 는 여러 Display 클래스들에 의해 구현되어 지고 이 Display 클래스들은 WeatherData 클래스 객체를 맴버 변수고 갖고 있어서 생성자가 호출될 때 WeatherData 객체를 넘겨 받아서 넘겨받은 WeatherData의 add 함수를 호출해서 WeatherData의 observer 맴버 변수 배열에 Display 자기 자신을 등록한다.
• Decorator pattern : decorator pattern에서는 객체에 추가적인 요건을 동적으로 첨가한다. 데코레이터는 서브클래스를 만드는 것을 통해서 긴능을 유연하게 확장할 수 있는 방법을 제공한다.
• 예제 : 스타버즈라는 커피숍의 주문 시스템을 만든다. 각 매뉴들을 표현하고 가격을 구현해야 한다. 
• 단순 답변 : Beverage라는 베이스 클래스를 만들고 새로 생기는 메뉴마다 이 슈퍼 클래스를 상속받는 서브 클래스를 만든다. 아니면 베이스 클래스에다가 서브 클래스에서 쓸 맴버 변수들을 포함시킨다. 이러한 경우 서브 클래스가 엄청 많아진다거나 혹은 서브 클래스가 필요하지도 않은 많은 맴버 변수들을 상속받게 된다.
• decorator pattern : 문제를 파악해보면 DarkRoast, HouseBlend, Decaf는 기본이 되는 음료가 되고 여기에다가 Mocha나 Whip (휘핑크림) 등은 decorator가 되겠다. 모든 음료의 기본이 되는 베이스 가상 클래스인 Beverage를 정의 하고 각종음료(DarkRoast, HouseBlend, Decaf)는 이를 상속하고 구현하는 구상 클래스가 되겠다. 그리고 decorator들(Mocah, Whip) 역시 Beverage 가상 클래스를 상속하게 한다. 이것의 목적은 Beverage로 부터 행동을 상속 받기 위함이 아니라 decorator의 형식과 각종 음료의 형식을 맞취기 위한 것이다. 확장되는 행동들은 decorator 안에 구현하고 decorator 안에는 또한 Beverage를 구성 요소로 갖는다. 결론적으로 기본음료를 decorator가 감싸고 이 감싼 객체를 또다른 decorator가 감싸는 형식으로 구현하는 것이다. 

디자인 원칙

1. 애플리케이션에서 달라지는 부분을 찾아내고, 달라지지 않는 부분으로부터 분리 시킨다.
2. 구현이 아닌 인터페이스에 맞춰서 프로그래밍한다.
3. 상속보다는 구성을 활용한다. 
4. 클래스는 확장에 대해서는 열려 있어야 하지만 코드 변경에 대해서는 닫혀 있어야 한다.

tabix

역시 Heng Li. 역시 장혜식님. 

GWAS

GWAS 란?
다음을 요약해보면..
일단 GWAS는 genome wide association study의 약자. 뭔말인고 하니 genome wide 하게 association study를 한다는 의미. 이건 또 무슨 말인고 하니 genome wide 하게 DNA를 관측하고 이 DNA의 차이 혹은 변화를 질병과 같은 변수와 연관지여 연구를 한다는 의미.
사람의 genome은 서로 99.9%가 동일하다. 그래서 차이는 거의 없을 거고 이 차이가 나름 중요한 역할을 할거다(질병이라던지 관련해서). 그럼 이 개인간의 차이 즉 common SNP은 몇개나 있을까? 10 million쯤 있을거라 생각되고.. 그럼 GWAS를 연구할려면 이 10M SNP를 다 detecting 해야 하냐? 아니다. 과학자들이 HapMap project라는 것을 진행해서 SNP의 조합인 haplotype들을 찾아놨기 때문에 돈은 많이 싸졌다. 물론 요즘 NGS 값이 워낙 싸서 더 싸졌다.




그럼 어떤식으로 GWAS를 진행할까?
많은 다수 그러니까 수천명 규모에서 수만명까지 특정 질병군(case)와 일반군(control)의 사람이 필요하고(이때 confounding factor인 성, 종족등을 통일(?)시킨다)


1.각각의 사람을 genotyping 한다. 그러니까 SNP를 찾는다.
2.quality control of genotype data.
3.genotype과 phenotype간의 통계적으로 연관이 있는지 확인. chi-squared 같은 걸 이용
4.연관된 주변의 추가적인 SNP의 genotyp으로 fine mapping of association signal. 그니까 3번 step에서 유의하다고 생각되는 snp 주변의 SNP들을 추가적으로 genotyping 해서 haplotype을 경험적으로다가 만들어 낸다.
5.그 담에 다른 집단에다가 적용. 이땐 지정된 SNP로다가만 testing 한다.
6.biological validation




 GWAS tools
많다. CRAN 의 task view의 genetics에서도 보면 GWAS를 할 수 있는 많은 package를 소개한다. 또한 broad institute 에서 만든 PLINK도 많이 사용한다.