|| (<-) || [Chap11] || StatisticalMethodsInBioinformatics || [Chap13] || (->) ||

=== '''12. Computationally Intensive Methods''' ===
 - Computing 집약적 방법들(?)

==== 12.1 Introduction ====

 * Computationally intensive method들이 computing power의 빠른 발전과 더불어 개발되어 왔고, 이렇게 개발된 도구들이 [Bioinformatics]에서 유용하게 쓰여지고 있다.
 * Estimation과 hypothesis testing을 위한 computationally intensive method들이 이 chapter에서 소개된다.
 
 * "plug-in" probability distribution :  
  * Probc(X=x) = mx/n (where, mx = 값이 x인 data의 갯수)
  * actual probability distribution of X
 * "plug-in" estimator
  * mean: Sum(xi)/n = xbar
  * variance: Sum((xi-xbar)^2)/n
  * 일반적으로, "plug-in" estimator는 random variable X의 "true" distribution에서 정의된 각 parameter를 구하는 공식으로 계산된다. (위의 "plug-in" mean과 "plug-in" variance와 같이)
  * "plug-in" estimate는 반드시 unbiased일 필요는 없다. 위의 "plug-in" variance는 biased estimate (but, if n->infinity, then bias->0 - Prob 12.1)

==== 12.2 Estimation ====

===== 12.2.1 Classical Estimation Methods =====

 * 표준편차를 가지고 classical estimator의 정확도를 평가하는 method를 설명 
 * X를 continuous random variable이라고 가정하고,
 * 첫번째 문제: A 값이 주어졌을 때, P( X < A )?
  * n개의 iid random variable의 측정치가 주어졌을 때, P( X < A ) = m/n (m은 A보다 작거나 같은 값을 가지는 측정치의 갯수)
  * P( X < A )는 binomial distribution을 갖는다고 하면, (3.11)식에서 m/n의 variance 값을 이용하여 P(X<A)의 95% confidence interval를 구할 수 있다.(3.12)식
 * 두번째 문제: p가 주어졌을 때, P( X < A ) = p를 만족하는 Ap?
  * p = i0/(n+1)이라고 했을 때, Ap = E(Xi0)
  * SD of Ap = root( p(1-p)/n(fx(Ap))^2 )
 * 위의 classical estimation method는 density funtion fX(x)을 알고 있을 때 사용가능하다. fX(x)를 모른다면, Ap뿐 아니라, 다른 parameter들도 classical 방법으로는 얻을 수 없다.

===== 12.2.2 Bootstrap Estimation and Confidence Intervals =====

 * 12.2.1의 classical 방법들의 한계를 극복하는 computational intensive method로 자주 사용되는 것에는 jacknife과 bootstrap이 있다. (이 책에서는 bootstrap을 설명)
 * Jacknife
  * ex) n iid observation인 X1, X2, ..., Xn이 주어졌을 때 Var(exp(xbar))를 구하라
   1. Sample X1, X2, ..., Xn에서 data를 하나씩 뽑아내어 sampling을 하는데 이 작업을 n번하여 n개의 sample을 만든다. 이 때 m번째 sampling에서는 Xm은 제외한다.
   2. 만든 sample로부터 variance를 각각 구한다. 이 때 m번째 sample의 variance를 T(X(m))이라고 하자
   3. Jacknife estimate of variance = ((n-1)/n) * Sum( (T(X(i)) - T(X(.)))^2 ) 이다.
  * 일반적으로, jacknife estimate는 다른 방법에 의한 estimate들보다 bias가 작다고 한다.
 * Bootstrap
  * Random variable X의 mean을 추정하고 그 추정치의 confidence interval를 구하고자 할 때, mean의 unbiased estimator xbar를 얻고, xbar가 normal distribution을 따른다는 가정하에, confidence interval를 구한다.(3.8) 하지만, estimator가 normal distribution이라고 가정할 수 없다면, (3.8)식은 적용될 수 없을 것이다.
  * Bootstrap의 기초가 되는 가정 (sample size가 충분히 크다면)
   * Discrete random variable의 경우에는 각 값들이 거의 sample에서의 frequency의 확률로 발생할 것이다.
   * Continuous random variable의 경우에는 특정 interval안의 값들이 관측될 확률은 sample에서 그 interval에 포함된 data의 비율이 될 것이다.   
  * Procedure
   1. X1, X2, ..., Xn의 n개의 sample에서 ''with replacement''방법으로 sampling을 m번한다.
    * Sampling ''with replacement'' : data set에서 random하게 하나를 뽑아내어 기록한 다음, ''뽑아낸 것을 다시 data set에 넣고'' 똑같은 과정을 반복한다.
   2. 1에서 얻은 bootstrap sample에서 각각 estimate를 계산한다.
   3. 2에서 얻은 n개의 estimate의 평균값이 bootstrap estimate가 된다.
  * Confidence interval구하기
   * 다양한 방법이 있다. 여기서는 두 가지를 설명한다.
   * 첫번째 방법: estimator의 variance에 대한 bootstrap estimate를 이용한다. (12.6)식. confidence interval구하는 방법은 two standard deviation rule를 이용한다.
   * 두번째 방법: quantile method. estimate의 2.5%가 A값 아래에 있고, estimate의 2.5%가 B값 위에 있을 때, (A, B)를 95% ''quantile'' bootstrap confidence interval이라고 한다.
  * Example
   * Golub et al의 gene intensity data는 그 분포가 trimodal형태로, 어떤 표준 분포와도 비슷한 모양이 아니다. 이 data를 가지고 bootstrap평균을 구했는데, 5.408로 sample average인 5.407에 거의 근접하였다. 또한 95% quantile bootstrap confidence interval (4.77, 6.09)도 (3.9)식에 의해 계산된 (4.73, 6.09)와 거의 같았다.
  * [[http://www.stanford.edu/class/stat208/]]

==== 12.3 Hypothesis Testing: The Bootstrap Alternative to the Two-Sample t-Test ====

 * Two-Sample t-Test: 두 group사이의 test statistic을 구하고 그 값이 유의미한지 test하는 것
  * test statistic in two-sample t-test
   1. t statistic (3.19)식
   2. x1bar - x2bar
   3. "unequal variance" t' statistic (8.49)식
 * Alternatives to the Two-Sample t-Test: [Permutation] test, Bootstrap
  * test statistic이 어떤 distribution을 가지는지 모른다면 test하기 어렵다.
  * 따라서 그것의 대안으로서 [Permutation] test와 Bootstrap은 test statistic값들을 아주 많이 만들어내어, 이 data들의 distribution을 가지고 test하는 방법이다.
 * [Permutation] test (3.5)
  * Procedure: ex) size m인 group A와 size n인 group B 사이의 test statistic값이 Type I Error를 a%로 하여 유의미한지 test하라. -> H0 : two groups are equal. 따라서 H0이 rejection되면 유의미하다고 할 수 있다.
   1. group A와 group B 사이의 test statistic값 t를 구한다.
   2. group A와 group B를 합쳐서 섞고, size m인 random sample RA와 size n인 random sample RB를 만든다.
   3. RA와 RB의 test static을 계산한다. -> t'
   4. 2,3과정을 반복하여 test static을 아주 많이 만들어낸다.
   5. t'값들의 distribution을 통해 Type I Error a%를가지고 t값이 유의미한지 판단한다.
  * Disadvantage: 두 group의 variance가 같다는 가정이 있어야만 한다. 
 * Bootstrap test
  * Procedure
   1. (8.49)식을 사용하여 두 group의 "unequal variance" t' static을 구한다. -> t
   2. Bootstrap sampling을 하기 전, 두 group의 평균을 같도록 해주기 위해서, 두 group의 평균이 각각 0이 되도록 data를 보정한다. -> 보정된 group A', B'
   3. 각 group A', B'로 부터 12.2.2의 Bootstrap sampling방법으로 BA', BB'를 얻는다.
   4. BA'와 BB'로부터 "unequal variance" t' statistic을 계산한다.
   5. 3,4의 과정을 반복하여 t' statistic data를 많이 만들어낸다. -> bootstrap t' values
   6. bootstrap t'values의 분포를 통해 t값의 유의미성을 판단한다.
 * Bootstrap test가 [Permutation] test와 다른 세가지 중요한 성격
  1. Bootstrap sampling은 ''with'' replacement 방법이다. [Permutation] test는 ''without'' replacement 방법
  2. [Permutation] test처럼, t statistic (3.19)식과 x1bar-x2bar가 자동적으로 서로 단순한(monotonic) 관계가 되지 않는다.
  3. '''(most important)''' [Permutation] test는 비교하려는 두 group이 같은 distribution을 갖음을 (variance가 같아야 함) 가정해야 함에 비해 bootstrap은 그러한 가정이 필요없다.

==== 12.4 Multiple Testing Revisitied ====

===== 12.4.1 Introduction =====

 * Multiple Testing: 대량 테스트 (3.8)
  * ex) Two microarray 사이에서 발현 정도가 유의미하게 다른 gene 찾기. 
   * 1000개의 gene이 array에 있다면 1000개의 test가 필요하다. 각 gene이 두 cell type 사이에서 그 발현정도가 유의미하게 다른지를 판단하게 위해서 two-sample t-test를 이용한다. 이러한 multiple test에서 문제는 일반적으로(경험적으로) 실제로 발현정도가 다르게 나타나는 gene의 갯수는 아주 적은 비율이기 때문에 false negative의 수가 true negative의 수에 비교하여 아주 커진다는 것이다. 예를 들어, 실제로 1000개의 gene중에서 40개가 유의미하게 발현정도가 다르다고 할 때, false negative가 될 test의 갯수는 (1000-40)*0.5 = 48개로 1000개 test모두 옳은 판단을 했을 때 rejection되는 test의 수 40개보다 오히려 크다. 따라서 각각의 gene test에서 Type I Error 5%를 합리적으로 사용하였음에도 불구하고, 1000개의 test에서 rejection된 test의 판단이 틀릴 확률('''''experiment-wise'' Type I Error''')는 0.5가 아니고 훨씬 큰 값이 된다.
   * Formal definition of ''experiment-wise'' Type I Error : 모든 test의 가설이 참일때, 적어도 하나의 가설을 reject할 확률
   * ''experiment-wise'' Type I Error가 a%가 되게 하려면 각 test에서 사용할 Type I Error를 보정해야 한다.
    1. ''Bonferroni'' correction : a/g (g: gene의 갯수)
    2. ''Sidak'' procedure : K(g, a) = 1 - (1-a)^-g (2.157)식
 * One-step method : Multiple test를 할 때, 모든 test에서 똑같은 값의 Type I Error를 사용한다면, 하나의 test를 통해 다른 모든 가설을 검정할 수 있다. p-value가 가장 작은 test를 검증하는 것이다. 가장 작은 p-value가 Type I Error보다 크다면, 당연히 다른 test의 p-value들 모두 Type I Error 보다 크므로 accept되고, 반대의 경우도 가장 작은 p-value를 가진 test의 가설이 reject된다면, 다른 가설들도 모두 reject된다. 이 방법을 one-step method라고 한다.
 * Multiple Testing Problem : 위의 보정법이 ''experiment-wise'' Type I Error 값을 보장하긴 하지만, 각 test에서 사용하는 Type I Error값이 너무 작기 때문에, true rejection할 확률이 너무 작아지는 문제가 생기는데 이 문제를 ''multiple testing problem''이라고 한다. Step-Down method는 이 문제를 해결하기 위한 방법이다.

===== 12.4.2 Step-Down Methods: t-Tests =====
 * Procedure
  * 각 test의 p-value를 오름차순으로 정렬한다. p(1), p(2), ..., p(m), p(n), ..., p(g), p(m) < p(n)
  * Type I Error of p(j) = K( g-j+1, a ) : j가 커질수록 값이 커진다.
  * Step 1: if p(1) > K( g, a ), then all null hypothesis are accepted. -> end. OR, H0(1) is rejected and go Step 2
  * Step 2: if p(2) > K( g - 1, a ), then remaining all null hypothesis are accepted. -> end. Or, H0(2) is rejected nad go Step 3.
 * Step-Down Method를 사용했을 때 ''experiment-wise'' Type I Error가 과연 a가 되는가?
  * 첫번째 증명: p357 line 21 
  * 두번째 증명: p357 line 29
 * 장점 : p(1) > K(g, a)를 만족하여 p(1)이 H0(1)이 accept되었다면, p(1)이 test들 중 가장 작은 값이기 때문에 당연히 나머지 test의 가설들이 모두 accept된다. 이러한 점은 종래의 one-step 방법과 같다. 하지만, H0(1)이 reject되었을 때, H0(2)이 reject되는 조건 p(2) < K(g-1, a)이 one-step 방법의 p(2) < K(g, a)보다 덜 stringent하게 된다. 따라서 one-step method에서보다 false positive를 많이 줄일 수 있는 장점이 있다.
 * 단점 : false negative가 커질 수 있다.

  
===== 12.4.3 Step-Down Methods: A Permutation Test =====
===== 12.4.4 Step-Down Methods Applied to Expressions Arrays =====

==== Problems ====

==== Comments ====