BiologicalSequenceAnalysis에서 SequenceAlignment의 한 방법.

Contents

  1. Introduction
  2. What a multiple alignment means
  3. Scoring a multiple alignment
    1. Minimum entropy
    2. Sum of pairs:SP scores
  4. Multidimensional dynamic programming
    1. MSA
  5. Progressive alignment methods
    1. Feng-Doolittle progressive multiple alignment
    2. Profile alignment
    3. ClustalW
    4. Iterative refinement methods
  6. Multiple alignment by profile HMM training
    1. Multiple alignment with a known profile HMM
  7. Overview of profile HMM training from unaligned sequences
    1. Initial model
    2. Baum-Welch expectation maximization
    3. Avoiding local maxima
  8. Adaptively modifying model architecture; model surgery
  9. Etc.

Introduction

high quality MultipleAlignment가 필요

RNA alignment

automatic method

여기서는,

What a multiple alignment means

homologous residue( structurally & evolutionally sense)- align in column

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

highly identical seq.의 경우를 제외하고는, 구조적, 진화적 위치에 대한 identify와 correct' MultipleAlignment를 하는 것은 not possible.

Fig.6.2 -Chothia&Lesk, 1986

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
  2. evolutionary model is very complex
    • Evolutionary change 의 확률은 natural selection 에 의한 position-specific structural and functional 제약 뿐 아니라 evolutionary time 에 의존한다.
    • 이러한 모델 하에서 high-probability alignment 는 good structural and evolutionary alignment 가 될 것이다.
  3. 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' 가 관찰된 것을 계산

다양한 column - higher 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

SpScoreExampleInMultipleAlignment

Multidimensional dynamic programming

column들은 -statiscally independent

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

DynamicProgramming algorithm

Exercise 6.1

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 이상인 것만 계산하면 된다.

Progressive alignment methods

가장 일반적으로 사용하는 방법

PairwiseAlignment를 연속적으로 수행

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에 추가

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에 의해 결정된다는 것 

  - 1→→→n, n+1 →→→ N

  ∑_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 )

ClustalW

ClustalW

  1. 모든 sequence pair 에 대해서 Kimura 의 모델을 이용하여 evolutionary distance diagonal matrix 만든다.

  2. Neighbor-joining clustering algorithm을 사용하여 guide tree를 만든다.
  3. Similarity 가 감소하는 순으로, sequence-sequence, sequence-profile, and profile-profile alignment 한다.
  4. Various additional heuristics
  5. alignment를 score하기 위해 사용되는 substitution matrix
    • 근접한 seq.-'hard' matrix(BLOSUM 80)
    • 먼 seq. - 'soft'matrix(BLOSUM 50)
  6. hydrophobic residue들은 hydrophilic or flexible residue 보다 높은 panelty를 준다.
  7. gap-open panelty는 position에서 5개나 그 이상의 hydrophilic residue의 연속이나 그 이상이 오면 감소

Iterative refinement methods

progressive alignment의 문제점-subalignment가 'frozen'이다 라는 것. 즉, 한 group이 먼저 align → 이 alignment가 뒤에서는 바뀌어 질수 없다는 것

Multiple alignment by profile HMM training

ProfileHmm 은 BaumWelchAlgorithm을 사용하여 unaligned sequence 로부터 train 되어질 수 있다.

Multiple alignment with a known profile HMM

MultipleAlignment를 가지고 있고, 또 family에서 나온 대표적인 set의 model을 가지고 있을 때, 다른 family member에 align하기 위해 이들이 사용되어지길 바라는데, ProfileHmm에 하나의 seq를 어떻게 align 하는지 보면....

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를 사용하기 위해 필요

  2. 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)

Adaptively modifying model architecture; model surgery

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

  1. match state 중에서 불필요한 것이 있어서 insert state 로 흡수되어야 하는 것
  2. 하나 또는 그 이상의 insert state 가 너무 많은 sequence를 가지고 있어서 더 많은 match state 가
    • insert state 의 전 또는 후에 삽입되어야 할 경우

이는

  1. Model length 의 initial choice 가 적당하지 않은 경우
  2. 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/

MultipleAlignment (last edited 2011-08-03 11:00:49 by localhost)