BiologicalSequenceAnalysis에서 SequenceAlignment의 한 방법.

||<<TableOfContents>>||

== Introduction ==
high quality MultipleAlignment가 필요
 -> ''[[Protein]] sequence 진화에 대한 전문적 지식''( comes from experience )을 이용하여 수동으로 진행

    some factor
     - specific sorts of columns in alignment
      (highly conserved residue or hydrophobic residue)-> secondary, tertiary structure에 영향
     - B-sheet에서의 hydrophobic과 hydrophilic
     - insertion and deletion pattern

RNA alignment
    sequence에서 추론된 alignment는 2차 구조 model에서 많이 다를 수 있다.

automatic method
   높은 점수를 갖는 MultipleAlignment를 찾음

여기서는,
    - 구조적, 진화적으로 multiple sequence alignment method
     -> ProfileHmm에 의한 full probabilistic multiple alignment로 접근..
    - other method & ProfileHmm을 비교

== What a multiple alignment means ==

homologous residue( structurally & evolutionally sense)- align in column
    -> 유사한 3차 구조적인 위치와, common ancestor로 부터 분화

'''Fig 6.1''' Ig superfamily sequences : manually alignment based on expert structural knowledge.

highly identical seq.의 경우를 제외하고는, 구조적, 진화적 위치에 대한 identify와 correct' MultipleAlignment를 하는 것은 not possible.
    → protein 구조는 진화하기 때문에 서로 다른 서열을 가진 2개의 protein을 align하기는 어려움

'''Fig.6.2''' -Chothia&Lesk, 1986
 - 여러개의 다른 protein family에서 pairwise structural alignment를 조사
  +- 30% identical
  +- only 50% of the individual residues were superposable in the two structures

  +- in principle - even if the structure diverge-명백히 correct evolutionary alignment가 있다.

  +- in practicle - 진화적으로 맞는 alignment는 structural alignment보다 어렵다.
                    (evolution history not known)
case of interest - 30% average pairwise seq.를 갖는 protein family

'''keep in mind - there is no objective way to define an unambiguously correct alignment'''

== Scoring a multiple alignment ==

 1. scoring system
  * position-specific scoring
  * sequences are not independent, related by phylogenic tree

 1. evolutionary model is very complex
  * Evolutionary change 의 확률은 natural selection 에 의한 position-specific structural and functional 제약 뿐 아니라 evolutionary time 에 의존한다.
  * 이러한 모델 하에서 high-probability alignment 는 good structural and evolutionary alignment 가 될 것이다.

 1. alignment의 개개의 column은 통계학적으로 independent 하다고 가정
  * scoring function
   {{{
    S(m)=G + ∑S(mi)
                     S(mi) = score for column
     G = a function for scoring the gaps that occur in the alignment
     
                     mi = column i of the multiple alignment m
   }}}

  * if gap을 하나의 residue로 처리할 경우 S(m) = ∑S(mi) but gap residue를 독립적으로 처리 하지 않음

=== Minimum entropy ===

Cia=∑δ(mij=a) → column i에서 'a' 가 관찰된 것을 계산
 
                   
    P(mi) = ∏ Pia^Cia (6.2) (Pia = column i 에서 residue a 의 확률)
              a

    S(mi) = -∑Cia log Pia (6.3) (align 된 residue의 column에서 관찰된 다양성의 측정)

다양한 column - higher entropy
 * completely conserved column - entropy '0'

 * Good Alignment 는 total entropy를 최소화 하는 것

실제적으로 우리는 PseudoCount 나 DirichletPrior 로 normally regularize 한다.

=== Sum of pairs:SP scores ===

column 들은 SubstitutionMatrix 를 이용한 ''' sum of pairs '''
   
column의 SP score는 S(mi) = ∑ S(mi-k, mi-l) PAM or BLOSUM의 SubstitutionMatrix로부터 온 값
 
MultipleAlignment = '''''three-way alignment''''' , log(Pabc/QaQbQc)
 
There is no probabilistic justification of the SP score
 ; each sequence is scored as if it descended from the N-1 other sequences instead of a single ancestor.

SpScoreExampleInMultipleAlignment

== Multidimensional dynamic programming ==
 
column들은 -statiscally independent
 - gap cost γ(g) =gd g=gap length, d= gap cost

(6.7)의 식과 (6.8)의 식을 plus = (6.9) 2^N -1

DynamicProgramming algorithm
 sequence length = L
 
 SpaceComplexity '''O(L^N)'''
   
 TimeComplexity '''O(2^N L^N)'''

'''Exercise 6.1'''
 number of sequence - 50 residues two - seq.를 pairwise align 하는데 0.5 sec 소요 4개의 seq.를 alignment 하는데 (2L)^N-2=10^4 sec ( a few hours) unlimited memory, five billion years( = 50억년)
  ''how many sequence could our computer align?''

    ---> about '''10''' sequence
  
=== MSA ===
    
Multidimensional DynamicProgramming 의 volume을 줄이는 algorithm을 사용
  
적절한 length(200~300 residues)의 5~7 protein sequence를 optimally align
{{{
   a^kl: pairwise alignment between sequence k and l

   a^ ^kl: optimal pairwise alignment of k, l

   S(a) = ∑{k<l} S(a^kl )로 두면

   S(a^kl ) ≤ S(a^"^kl" )

   σ (a) ~≤~ S(a^kl ) - S(a^"^kl" ) + ∑{k'<l'} S(a^"^k'l'`" )

   σ (a) : optimal alignment 의 good bound

   '''S(a^kl ) ~≥~ σ (a) + S(a^"^kl" ) - ∑{k'<l'} S(a^"^k'l'`" ) ~=~ β ^kl '''
}}}
그러므로 k 와 l 의 pairwise alignment 는 β^kl 의 score 이상인 것만 계산하면 된다.
 β^kl(lower bound)은 쉽게 계산되어진다.

== Progressive alignment methods ==
  
가장 일반적으로 사용하는 방법
  
PairwiseAlignment를 연속적으로 수행
 * 초기에 2개의 서열을 선택 → standard pairwise alignment에 의해 align → 고정 → 세 번째 seq.를 선택
  → 고정된 align과 align → 모든 서열을 반복
  
 * 차이점
  1. alignment를 하기 위해서 순서를 고르는 방법
  1. in whether the progression involves only alignment of sequences to a single growing alignment or whether
       subfamilies are built up on a tree structure and, at a certain points, alignments are aligned to alignments
  1. in the procedure used to align and score sequences or alignments against existing alignments

 * 장점 : fast and efficient
   
  1. 가장 중요한 heuristic은 가장 유사한 sequence pair를 먼저 align
  
  2. 대부분의 algorithm 은 'guide tree'를 만든다.
      But guide trees are typically 'quick and dirty' trees unsuitable for serious phylogenetic inference.

=== Feng-Doolittle progressive multiple alignment ===
  
① standard pairwise alignment에 의해 N seq.의 모든 pair들 사이에서 N(N-1)/2의 diagonal matrix를 계산

② clustering algorithm을 이용한 distance matrix로부터 guide tree를 만든다.

③ 1st node에서 시작하여 child node(seq-seq, seq-alignment, alignment-alignment)에 align하여 tree에 추가
  → 모든 seq.가 align 될 때까지 반복

purpose is 대략적인 guide tree를 만드는 것
{{{
   - D = -log Seff = -log{(Sobs-Srand)/(Smax-Srand)}
}}}

scoring system = PAM score

완전한 alignment후에 gap은 neutral X character로 대치


'''"once a gap, always a gap"'''

=== Profile alignment ===

Feng-Doolittle 방법의 문제점 -모든 alignment들은 pairwise seq alignment에 의해 결정된다는 것

 * align된 group이 하나 있다고 가정하고,이 group에 새로운 seq.를 align할 때, group내의 multiple-alignment로부터 position specific information을 사용한다.
  
 * seq conservation degree는 다양한 곳에서의 mismatch보다 highly conserved 위치에서 mismatch 된것에 과하게 부과
  
 * gap penalty도 gap이 많은 곳에서는 감소, gap이 없는 곳에서는 증가
{{{
  - 1→→→n, n+1 →→→ N
}}}
  이것의 score 는 2개의 profile 에 관련된 sum 과 한 개의 모든 cross term을 포함하는 sum 으로 나누어진다.
{{{
  ∑_i S(m_i ) =
  ∑_i ∑_{k<l≤N} s(m_i^k , m_i^l )

  = ∑_i ∑_{k<l≤n} s(m_i^k , m_i^l ) + ∑_i ∑_{n<k<l≤N} s(m_i^k , m_i^l ) + ∑_i ∑_{k≤n, n<l≤N} s(m_i^k , m_i^l )
}}}
  두 profile 의 optimal alignment 는 cross term을 가진 마지막 sum을 optimizing 함으로써 얻어진다.

=== ClustalW ===
[[ClustalW]]
   
 1. 모든 sequence pair 에 대해서 [[Kimura 의 모델]]을 이용하여 evolutionary distance diagonal matrix 만든다.
 1. Neighbor-joining clustering algorithm을 사용하여 guide tree를 만든다.
 1. Similarity 가 감소하는 순으로, sequence-sequence, sequence-profile, and profile-profile alignment 한다.
 1. Various additional heuristics

 * alignment를 score하기 위해 사용되는 substitution matrix
  * 근접한 seq.-'hard' matrix(BLOSUM 80)
  * 먼 seq. - 'soft'matrix(BLOSUM 50)

 * hydrophobic residue들은 hydrophilic or flexible residue 보다 높은 panelty를 준다.

 * gap-open panelty는 position에서 5개나 그 이상의 hydrophilic residue의 연속이나 그 이상이 오면 감소


=== Iterative refinement methods ===
   
progressive alignment의 문제점-subalignment가 'frozen'이다 라는 것. 즉, 한 group이 먼저 align → 이 alignment가 뒤에서는 바뀌어 질수 없다는 것
  
 * '''Algorithm : Barten& Sternberg multiple alignment'''
    
  1. 가장 높은 pairwise similarity를 가진 2개의 seq를 찾고 align
  1. 2개의 align된 profile에 가장 유사한 seq를 찾음 → seq-profile alignment에 의해 처음 2개에 align → 반복
  1. X1을 제거하고 X2~XN의 profile을 realign→ 반복
  1. 이것을 alignment score 가 converge 할 때까지 정해진 숫자만큼 반복한다.

== Multiple alignment by profile HMM training ==
  
ProfileHmm 은 [[BaumWelchAlgorithm]]을 사용하여 unaligned sequence 로부터 train 되어질 수 있다.
   → 이를 통해서 model 도 만들고 alignment 도 할 수 있다.

=== Multiple alignment with a known profile HMM ===
  
MultipleAlignment를 가지고 있고, 또 family에서 나온 대표적인 set의 model을 가지고 있을 때, 다른 family member에 align하기 위해 이들이 사용되어지길 바라는데, ProfileHmm에 하나의 seq를 어떻게 align 하는지 보면....
   
 * model을 통해서 가장 가능성 있는 path를 ViterbiAlgorithm에 의해 찾는다.
 * residue들은 ProfileHmm match state에 align되고, column에서 align된다.
      
 * '''Fig 6.4''' Constructing a MultipleAlignment 는 단지 Viterbi 계산만 하면 된다
    
 * '''Fig 6.5''' The most probable paths of the seven sequences through the model.
    
 * '''Fig 6.6''' Viterbi path를 보고, multiple alignment하기 전에 insert state내의 maximum 수를 보고 상위에 위치하게 한다.
    
== Overview of profile HMM training from unaligned sequences ==
  
Algorithm : MultipleAlignment using ProfileHmm

 1. Initialization - profile HMM의 길이를 선택, parameter를 초기화

 1.Training - Baum-Welch나 ViterbiAlgorithm을 이용하여 model을 예측
         → LocalOptima를 피하기 위한 하나의 heuristic method를 사용하기 위해 필요

 1. MultipleAlignment - ViterbiAlgorithm을 이용한 final model을 만들기 위해 모든 seq를 align하고 MultipleAlignment를 만든다.

=== Initial model ===
   
BaumWelchAlgorithm estimation 의 초기 구조를 고르는데 유일하게 내려야 할 결정은 model M 의 length 이다. M 은 profile HMM 에서의 match state 의 숫자이다.

흔히 사용되는 규칙은 M을 training sequence 들의 average length 로 두는 것이다.

Baum-Welch estimation 은 global 이 아닌 LocalOptima를 찾기 때문에 시작 model을 주의깊게 고르는 것이 필요하다.

=== Baum-Welch expectation maximization ===
  
Forward & Backward variables can then be combined to re-estimate emission and TransitionProbability parameters
  
Baum-Welch re-estimation procedure can be replaced by the Viterbi alternative
   
=== Avoiding local maxima ===

One way to search the parameter space is different(random) initial model로부터 여러번 다시 시작하는 것이고, best scoring final one을 지키는 것
     
A more involved approach is to use some form of stochastic search algorithm (=SimulatedAnnealing)

 '''1. Theoretical basis of SimulatedAnnealing'''
      High temperature 를 줘서 system을 molten 상태로 만든 다음, 점진적으로 temperature를 낮춘다.
       보통 [[MonteCarloMethod]] 로 불린다.

       (높은 온도를 주면... systme 이 molten 된 상태가 되어 움직임이 자유로와져서 (확률적으로) 이제까지 넘어갈 수
        없었던 부분을 넘어버릴 수 있어서 local optima를 탈출하고,그 상태에서 다시 온도가 낮아지면,
        새로운 optima에서 안정됨. stochastic choice 이기 때문에 Monte Carlo method 임.)

 '''1. simulated annealing Viterbi estimation of HMMs'''
      
       Viterbi 가 each sequence 에 대한 highest probability path 파이 를 찾는데 비하여
       simulated annealing 에서는 temperature T 에 따라서 suboptimal path 파이가 확률적으로 선택된다.
       Suboptimality 의 degree 는 처음에 높게 시작해서 천천히 감소되는 temperature factor T에 의해서 조절된다.
       Temperature를 얼마나 빨리 떨어뜨릴 것인가를 정하는 것은 그 자체로 science (혹은 art) 에 속하는 일이다.

 '''1. Noise injection during Baum-Welch HMM re-estimation'''
     SimulatedAnnealing의 중요한 point는 configuration의 stochastic choice 때문에 LocalMinima를 피하는 것이 가능하다는 것
  
     similar effect forward-backward 과정에서 예측된 count에 noise를 첨가하고 천천히 줄여주면 simulated annealing과 같은효과

     simulated annealing에서 temp가 감소한 만큼 noise의 size를 감소시킨다.

 '''1. Comparison to Gibbs sampling'''
     GibbsSampling algorithm 은 근본적으로 유사성을 가진다. by Lawrence(1993)
  
     * Lawrence가 사용했던 statistical model은
        short upgapped motif model, insert or delete state가 없는 ProfileHmm
  
     * training data는 some motif(specific protein-binding site on DNA)를 가진 하나의 seq set으로 구성
  
     * 문제는 - motif position을 찾는 것, 통계적 model에 대한 parameter를 estimation

        - site sampler - most basic implementation of the Gibbs sampler
               there is exactly one motif element located within each sequence

        - motif sampler - more flexible, and complex
       allowing for 0 or more occurrences of a motif within each of the sequences
          
           ⇒ two sampler - allow for the discovery of different motifs within the sequences


== Adaptively modifying model architecture; model surgery ==

Model을 training 한 다음에는 다음과 같은 경우를 살펴야 한다.

 1. match state 중에서 불필요한 것이 있어서 insert state 로 흡수되어야 하는 것

 1. 하나 또는 그 이상의 insert state 가 너무 많은 sequence를 가지고 있어서 더 많은 match state 가
    insert state 의 전 또는 후에 삽입되어야 할 경우

이는

 1. Model length 의 initial choice 가 적당하지 않은 경우

 1. training 중에서 local optima를 만났을 경우에 발생한다.

이때에는 model architecture 의 변경이 필요하다.

 1. model surgery

 2. Re-estimation both a model architecture and model parameters
    using the maximum a posteriori (MAP) model constructuion algorithm


** '''HiddenMarkovModel, GibbsSampling - probablistic'''

** '''[[ClustalW]], [[MACAW]] - heuristic'''

== Etc. ==
튜토리얼 http://bioinformatics.weizmann.ac.il/~pietro/Making_and_using_protein_MA/