(55) Multiple Sequence Alignment by 3-dim DP

	Machine:     PIM
	Environment: PIMOS, SIMPOS
	Language:    KL1, ESP
	Source Code: 0.5 MB
	Documents:   None

Overview

Configuration

Generator:

Generating a Process Network for DP calculation

Cost Evaluate Process:

Evaluating Costs and Proceed DP calculation

Function

Multiple alignment is powerful methodp to analyse the protein or DNA sequences, by which we can recognise the conserved parts considerd to be significant. This is an example of an alignment.

    --HEKLLHPGIQKTTKLF-GET--YY
    -LHQ-LTHLSFSKMKALLERSHSPYY
    ELHS-FTHCG---QTAL--TLQ----
      ^    ^        ^
      |    |        |
  

Here`-'s(gaps) are inserted in order for each column to have the same or similar amino acids. Multiple alignment problem may be considered as a combinatorial optimization problem and is solved by DP(i.e. dynamic programming)matching.

The conventional alignment programs use two dimensional DP because more than two dimensional requires a large amount of calculation. Our program impremented on PIM, however, calculates three dimensional DP in a practical time owing to two parallelism: 1) parallel calculation along the wave front in DP process network;2)pipeline parallel calculation.

Three dimensional DP improved the quality of multiple alignment significantly.

FTP

• Multiple Sequence Alignment by 3-dim DP [93K]