Multiple Sequence Alignment

多序列並列分析

由雙序列並列分析的討論中，可以知道 dynamic programming 可以找到最佳的並列方式。若在三維，甚至高維空間中做 dynamic programming，在理論上可以找到多序列的最佳並列方式。因為嚴謹地並列分析會佔用非常大的記憶體空間，並且非常耗時。在實際上此法速度太慢，所以一般是採用漸近式的雙序列並列分析來做，以增加程式運作的效率。例如----在 GCG 中的 PileUp 用一種在建立親緣樹時，最簡單的運算法─UPGMA (unweighted pair-group method using arithematic averages)。

假設我們想找出與 5S rRNA 有關的所有序列，以便經由多序列並列分析找到守舊的區域。只靠關鍵字的搜尋是不夠的，較好的實驗設計是先找到一個典型的 5S rRNA 序列，再找出在資料庫中所有和它相似的序列，這種方法乃是利用 similarity search 來收集序列的例子。

Suggestions

注意事項

不保證產生最佳並列分析的結果

在做並列的過程中如果要插入空隙，則該群序列中的每個序列都會在同樣的位置插入空隙。像這樣漸進的，兩兩並列的方法所得的並列分析結果，會與哪一個序列先參與並列分析有關。目前所採用的方法，只有在演化速率相當時才能用，否則就無法得到滿意的結果。可是這種運作的方式與比對的順序有關，以不同的順序做比對，可能會產生不同的並列方式，換言之，利用這種省時間的漸近式雙序列比對，並不保證能找到最佳的並列方式。

此外，在比對時若序列太不像，程式就會一直引入空隙，以至於所得到之並列結果沒有任何意義。因此程式預設最多插入 2000 個空隙，超過此值，程式就會自動停止，以免印出沒有意義的結果，由此可知，若將多個只有小部份區域相似的序列放在一起是無法找到共有序列(conseusus) 的，即使是相似的基因，若不妥善處理，也可能會有問題。

必須用人工修正分析結果

在做完多序列並列分析之後，最好再做人工的修正。在人工修正時，除了調整沒有配對好的位置外，有一點很重要的是查看空隙的分佈是否合理，如圖所示的兩種狀況，一種是有一個較大的空隙和一個誤配，而另一種是有兩個分開的空隙。以得分來看，兩個分離的空隙就要扣兩次開啟空隙的罰分，若引進空隙的罰分設的太小，就可能產生圖 b 的情形。
可是由演化的角度來看，圖 b 所代表的是兩次獨立的突變事件，而圖 a 可能代表的是一次突變的事件，因此前者較難產生。若並列分析的結果中有許多分散的空隙，就代表罰分設的太低，需要調整罰分，重排一次後，再做人工修正。在做雙序列並列分析時，可利用開空隙的罰分與延伸空隙的罰分調整空隙插入的方式。在多序列並列分析時有時可能會因遷就已有的並列結果而插入不恰當的空隙，所以才需人的參與。
LineUp 程式是一個多序列編輯器，在使用上與做 DNA 序列分析時用的 GelAssemble(本課程不教)、和序列編輯器 SeqEd 的使用很相似。它也分為全螢幕與指令兩種模式。在全螢幕模式，它與 SeqEd 程式差異不大，在方盒 0-3中粗體字部份是在多序列下比較有用的功能鍵。

方盒 -3 LineUp 編輯器的使用 - 全螢幕模式棅癏

                        Screen Mode
                [n] is an optional numeric parameter.
G, A, T, C ....  - inserts a sequence character
<Delete>         - deletes a sequence character, "drags" a 
                   sequence to the left if cursor is at its 
                   start
<Space bar>      - "pushes" a sequence to the right if cursor 
                   is at its start
/TAACG<Return>   - finds the next occurrence of "TAACG", last 
                   pattern is the default when none is 
                   specified
[n]<Right-arrow> - move ahead [n characters]
[n]<Left-arrow>  - move back [n characters]
[n]<Up-arrow>    - move up to next sequence [or to row 
                   specified]
[n]<Down-arrow>  - move down to next sequence [or to row 
                   specified]
[n]<Return>      - move to column n
<Ctrl>H          - move to start of current sequence
<Ctrl>E          - move to end of current sequence
<Ctrl>R          - redraw the screen
<Ctrl>D          - enter Command Mode
<Ctrl>I          - push over all seqs starting past current 
                   column
<Ctrl>P          - pull over all seqs starting past current 
                   column
[n]<             - move 50 [or n] positions to left
[n]>             - move 50 [or n] positions to right

在指令模式下，它與 SeqEd 有較大的差距。它增加了讀取、新編、移動、除去單一序列的功能，也允許使用含糊 (ambiguous) 的序列代碼來搜尋字串。在檔案輸入與輸出方面，它支援檔名檔案與 msf 的格式。

方盒 -4 LineUp 編輯器的使用 - 指令模式

                              Command Mode
               x and y represent numbers for column and row.
           Only the capitalized part of the command is necessary.
[x,y] Get [filename]   - add sequence [at position x,y] [from 
                         filename]
[x,y] New [seqname]    - add empty sequence [at position x,y] 
[named seqname]        - move current or specified sequence
[to x,y]               - delete current or specified sequence 
                         entirely
REName [old] [new]     - change sequence name (changing consensus 
                         name changes the group)
REDraw                 - redraw the screen
HEAding [seqname]      - edit documentary heading of current or 
                         specified sequence
screen                 - enter screen mode (pressing <Return> is
                         sufficient)
NUCleotide             - use nucleotide ambiguity codes in find and 
                         consensus
PROtein                - do not use nucleotide ambiguity codes
SPacewalk              - use spacewalk to position sequences 
NOSPacewalk            - DO NOT use spacewalk to position sequences 
FOSN                   - use list file format when writing
MSF                    - use multiple sequence format files when 
                         writing
[n] SLide              - add n to all sequence columns
[s,f] ROWMove [n]      - move a set of rows (s to f) up or down 
                         [n rows]
[s,f] PRint [filename] - write the sequence group to a Pretty 
                         format file
SUMmary [filename]     - write the sequence names and positions
                         in a file or on the terminal screen
GOto [seqname]         - put cursor on start of named sequence
[s,f] CONSensus        - calculate consensus [from s to f]
AUtoconsensus          - automatically calculate consensus (slow)
NOAUtoconsensus        - turn off automatic consensus
FLip                   - reverse complement the current group
ZIp [filename]         - align and gap a sequence to the current 
                         group
Write [filename]       - write the current sequence group to a file
EXit [filename]        - write the current group to a file and stop
Quit                   - quit the editor without writing out the
                         group
Press <Return> to return to LINEUP:

建議的方法
因為目前用來做多序列並列分析的程式，多不保證找到最佳的並列方式，因此最好的策略是試用不同的方法做，再相互參照，以尋找符合需求的結果。

Examples

5S rRNA (Use FastA or Local Blast for preliminary alignment)
Zinc fingers within TFIIIA (Use Compare / DotPlot for preliminary alignment)
Consensus sequence of the zinc finger (Use FastA or Local Blast for preliminary alignment)

Last updated on 11/27/01