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가 필요

  • -> 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
  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' 가 관찰된 것을 계산

  • 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

Exercise 6.1

  • number of sequence - 50 residues two - seq.를 pairwise align 하는데 0.5 sec 소요 4개의 seq.를 alignment 하는데 (2L)N-2=104 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를 하기 위해서 순서를 고르는 방법
    2. 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
    3. 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 만든다.

  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가 뒤에서는 바뀌어 질수 없다는 것

  • Algorithm : Barten& Sternberg multiple alignment

    1. 가장 높은 pairwise similarity를 가진 2개의 seq를 찾고 align
    2. 2개의 align된 profile에 가장 유사한 seq를 찾음 → seq-profile alignment에 의해 처음 2개에 align → 반복
    3. X1을 제거하고 X2~XN의 profile을 realign→ 반복
    4. 이것을 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를 사용하기 위해 필요

  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)

  • 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 로 흡수되어야 하는 것
  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)

web biohackers.net