# Presentation: 483897

## Algorithms for Alignment of Genomic Sequences

- Michael Brudno
- Department of Computer Science
- Stanford University
- PGA Workshop 07/16/2004

## Conservation Implies Function

- Exon

- Gene

- CNS:
- Other
- Conserved

## Edit Distance Model (1)

- Weighted sum of insertions, deletions & mutations to transform one string into another
- 	**A****GG****CACA****--****CA         A****GG****CA****CA****CA**
- 	|  ||||  ||   or          |  ||  ||
- 	**A****--****CACA****TT****CA         A****CA****CA****TT****CA**

## Edit Distance Model (2)

- Given:		x, y
- Define:	F(i,j) = Score of best alignment of
- 			x1...xi to y1...yj
- Recurrence:	F(i,j) = max (	F(i-1,j) – GAP_PENALTY,
- 					F(i,j-1) – GAP_PENALTY,
- 					F(i-1,j-1) + SCORE(xi, yj))

## Edit Distance Model (3)

- F(i,j) = Score of best alignment ending at i,j
- Time O( n2 ) for two seqs, O( nk ) for k seqs

- F(i,j)

- F(i,j-1)

- F(i-1,j-1)

- F(i-1,j)

- AGTGCCCTGGAACCCTGACGGTGGGTCACAAAACTTCTGGA

- AGTGACCTGGGAAGACCCTGACCCTGGGTCACAAAACTC

## Overview

- Local Alignment (CHAOS)
- Multiple Global Alignment (LAGAN)
- 	-	Whole Genome Alignment
- Glocal Alignment (Shuffle-LAGAN)
- Biological Story

## Local Alignment

- F(i,j) = max (F(i,j), 0)
- Return all paths with   a position i,j where F(i,j) > C
- Time O( n2 ) for two seqs, O( nk ) for k seqs

## Heuristic Local Alignment

- BLAST

- FASTA

## CHAOS: CHAins Of Seeds

- Find short matching words (seeds)
- Chain them
- Rescore chain

## CHAOS: Chaining the Seeds

-   Find seeds at current **location **in *seq1*

**location**
- in seq1

- seed

*seq2*

## CHAOS: Chaining the Seeds

**location**
- in seq1

**distance**
- cutoff

- seed

*seq2*

-   Find seeds at current **location **in *seq1*

## CHAOS: Chaining the Seeds

**location**
- in seq1

**distance**
- cutoff

**gap**
- cutoff

- seed

*seq2*

-   Find seeds at current **location **in *seq1*

## CHAOS: Chaining the Seeds

-   Find seeds at current **location **in *seq1*
-   Find the previous seeds that fall into the search box

**location**
- in seq1

**distance**
- cutoff

**gap**
- cutoff

- seed

- Search
- box

*seq2*

## CHAOS: Chaining the Seeds

-   Find seeds at current **location **in *seq1*
-   Find the previous seeds that fall into the search box
-   Do a range query: seeds are indexed by their diagonal

**location**
- in seq1

**distance**
- cutoff

**gap**
- cutoff

- seed

- Search
- box

*seq2*

- Range of search

## CHAOS: Chaining the Seeds

-   Find seeds at current **location **in *seq1*
-   Find the previous seeds that fall into the search box
-   Do a range query: seeds are indexed by their diagonal.
-   Pick a previous seed that maximizes the score of chain

**location**
- in seq1

**distance**
- cutoff

**gap**
- cutoff

- seed

- Search
- box

*seq2*

- Range of search

## CHAOS: Chaining the Seeds

-   Find seeds at current **location **in *seq1*
-   Find the previous seeds that fall into the search box
-   Do a range query: seeds are indexed by their diagonal.
-   Pick a previous seed that maximizes the score of chain

**location**
- in seq1

**distance**
- cutoff

**gap**
- cutoff

- seed

- Search
- box

*seq2*

- Range of search

- Time O(n log n), where n is number of seeds.

## CHAOS Scoring

- Initial score = # matching bp - gaps
- Rapid rescoring: extend all seeds to find optimal location for gaps

## Overview

- Local Alignment (CHAOS)
- Multiple Global Alignment (LAGAN)
- 	-	Whole Genome Alignment
- Glocal Alignment (Shuffle-LAGAN)
- Biological Story

## Global Alignment

- AGTGCCCTGGAACCCTGACGGTGGGTCACAAAACTTCTGGA

- AGTGACCTGGGAAGACCCTGACCCTGGGTCACAAAACTC

## LAGAN: 1. FIND Local Alignments

- Find Local Alignments
- Chain Local Alignments
- Restricted DP

## LAGAN: 2. CHAIN Local Alignments

- Find Local Alignments
- Chain Local Alignments
- Restricted DP

## LAGAN: 3. Restricted DP

- Find Local Alignments
- Chain Local Alignments
- Restricted DP

## MLAGAN: 1. Progressive Alignment

- Given N sequences, phylogenetic tree
- Align pairwise, in order of the tree (LAGAN)

- Human

- Baboon

- Mouse

- Rat

## MLAGAN: 2. Multi-anchoring

- X

- Z

- Y

- Z

- X/Y

- Z

- To anchor the (X/Y), and (Z) alignments:

## Cystic Fibrosis (CFTR), 12 species

- Human sequence length: 	1.8 Mb
- Total genomic sequence:	 13 Mb

- Human

- Baboon

- Cat

- Dog

- Cow

- Pig

- Mouse

- Rat

- Chimp

- Chicken

- Fugufish

- Zebrafish

## CFTR (cont’d )

- 90

- 550

- 99.7%

- Mammals

- LAGAN

- 90

- 862

- 96%

- Chicken & Fishes

- Chicken & Fishes

- Mammals

- 670

- 4547

- 99.8%

- MLAGAN

- 98%

- MAX MEMORY (Mb)

- TIME (sec)

- % Exons
- Aligned

## Automatic computational system for comparative analysis of pairs of genomes 

- http://pipeline.lbl.gov
**Alignments (all pair combinations):**
- Human Genome (Golden Path Assembly)
- Mouse assemblies: Arachne, Phusion (2001)  MGSC v3 (2002)
- Rat assemblies:  January 2003, February 2003
- ----------------------------------------------------------
- D. Melanogaster vs D. Pseudoobscura  February 2003

## Tandem Local/Global Approach

- Finding a likely mapping  for a contig (BLAT)

## Progressive Alignment Scheme

- yes

- no

- yes

- no

- Human, Mouse and Rat genomes

- Pairwise M/R mapping

- Aligned M&R fragments

- Unaligned M&R sequences

- Map to Human Genome

- Mapping aligned fragments by union of M&R local BLAT hits on the human genome

- H/M/R MLAGAN alignment

- M/R pairwise alignment

- M/H and R/H pairwise alignment

- Unassigned M&R DNA fragments

- yes

- no

## Computational Time

- 23 dual 2.2GHz Intel Xeon node PC cluster.
-    Pair-wise rat/mouse – 4 hours Pair-wise rat/human and mouse/human – 2 hours Multiple human/mouse/rat – 9 hours
- Total wall time: ~ 15 hours

## Distribution of Large Indels

## Evolution Over a Chromosome

## Overview

- Local Alignment (CHAOS)
- Multiple Global Alignment (LAGAN)
- 	-	Whole Genome Alignment
- Glocal Alignment (Shuffle-LAGAN)
- Biological Story

## Evolution at the DNA level

- ...ACGGTGCAGTTACCA...

- ...AC----CAGTCCACCA...

- Mutation

- SEQUENCE EDITS

- REARRANGEMENTS

- Deletion

- Inversion

- Translocation

- Duplication

## Local & Global Alignment

- AGTGCCCTGGAACCCTGACGGTGGGTCACAAAACTTCTGGA

- AGTGACCTGGGAAGACCCTGAACCCTGGGTCACAAAACTC

- Local

- Global

## Glocal Alignment Problem

- Find least cost transformation of one sequence into another using new operations

- Sequence edits
- Inversions
- Translocations
- Duplications
- Combinations of above

- AGTGCCCTGGAACCCTGACGGTGGGTCACAAAACTTCTGGA

- AGTGACCTGGGAAGACCCTGAACCCTGGGTCACAAAACTC

## Shuffle-LAGAN

- A glocal aligner for long DNA sequences

## S-LAGAN: Find Local Alignments

- Find Local Alignments
- Build Rough Homology Map
- Globally Align Consistent Parts

## S-LAGAN: Build Homology Map

- Find Local Alignments
- Build Rough Homology Map
- Globally Align Consistent Parts

## Building the Homology Map

- Chain (using Eppstein
- Galil); each alignment
- gets a score which is
- MAX over 4 possible
- chains.
- Penalties are affine
- (event and distance
- components)

- Penalties:
- regular
- translocation

- c)	inversion
- d)	inverted translocation

## S-LAGAN: Build Homology Map

- Find Local Alignments
- Build Rough Homology Map
- Globally Align Consistent Parts

## S-LAGAN: Global Alignment

- Find Local Alignments
- Build Rough Homology Map
- Globally Align Consistent Parts

## S-LAGAN Results (CFTR)

- Local

- Glocal

## S-LAGAN Results (CFTR)

- Hum/Mus

- Hum/Rat

## S-LAGAN Results (IGF cluster)

## S-LAGAN results (HOX)

- 12 paralogous genes
- Conserved order in mammals

## S-LAGAN results (HOX)

- 12 paralogous genes
- Conserved order in mammals

## S-LAGAN Results (Chr 20)

-  Human Chr 20 v. homologous Mouse Chr 2.
-  270 Segments of conserved synteny
-  70 Inversions

## S-LAGAN Results (Whole Genome)

|  | LAGAN | S-LAGAN |
| --- | --- | --- |
| Total | 37% | 38% |
| Exon | 93% | 96% |
| Ups200 | 78% | 81% |
| CPU Time | 350 Hrs | 450 Hrs |

-  Used Berkeley Genome Pipeline
-  % Human genome aligned with mouse sequence
-  Evaluation criteria from Waterston, et al 								(Nature 2002)

## Rearrangements in Human v. Mouse

- Preliminary conclusions:
-   Rearrangements come in all sizes
-   Duplications worse conserved than other rearranged regions
-   Simple inversions tend to be most common and most conserved

## What is next? 				(Shuffle)

- Better algorithm and scoring
- Whole genome synteny mapping
- Multiple Glocal Alignment(!?)

## Overview

- Local Alignment (CHAOS)
- Multiple Global Alignment (LAGAN)
- 	-	Whole Genome Alignment
- Glocal Alignment (Shuffle-LAGAN)
- Biological Story

## Biological Story

- Math1 (Mouse Atonal Homologue 1, also ATOH) is a gene that is responsible for nervous system development

## Align Human, Mouse, Rat & Fugu

## Detailed Alignment

- hum_a : CAATAGAGGGTCTGGCAGAGGCTC---------------------CTGGC @ 57336/400001
- mus_a : CAATAGAGGGGCTGGCAGAGGCTC---------------------CTGGC @ 78565/400001
- rat_a : CAATAGAGGGGCTGGCAGAGACTC---------------------CTGGC @ 112663/369938
- fug_a : TGATGGGGAGCGTGCATTAATTTCAGGCTATTGTTAACAGGCTCGTGGGC @ 36013/68174
- hum_a : CGCGGTGCGGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTGAGCGC @ 57386/400001
- mus_a : CCCGGTGCGGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTGAGCGC @ 78615/400001
- rat_a : CCCGGTGCGGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTGAGCGC @ 112713/369938
- fug_a : CGAGGTGTTGGATGGCCTGAGTGAAGCACGCGCTGTCAGCTGGCGAGCGC @ 36063/68174

## Can we align human & fly???

- CGCGGTGC-GGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTGAGCGCACTCTCCTTTCAGGCAGCTCCCCGGGGAG
- CCCGGTGC-GGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTGAGCGCACTCG-CTTTCAGGCAGCTCCCCGGGGAG
- CCCGGTGC-GGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTGAGCGCACTCG-CTTTCAGGCAGCTCCCCGGGGAG
-  GAGGTGTTGGATGGCCTGAGTGA-AGCACGCGCTGTCAGCTGGCGAGCGCTCGCG-AGTCCCTGCCGTGTCCCCG
- Melan       GCTACTCCAGCT-ACCACCTGCATGCAGCTGCACAGC
- Pseudo      GCCACTGAGACT-GCCACCTGCATGCAGCTGCACAGA

## Putting it all together

- CGCGGTGC-GGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTGAGCGCACTCTCCTTTCAGGCAGCTCCCCGGGGAG
- CCCGGTGC-GGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTGAGCGCACTCG-CTTTCAGGCAGCTCCCCGGGGAG
- CCCGGTGC-GGAGCGTCTGGAGCGGAGCACGCGCTGTCAGCTGGTGAGCGCACTCG-CTTTCAGGCAGCTCCCCGGGGAG
-  GAGGTGTTGGATGGCCTGAGTGA-AGCACGCGCTGTCAGCTGGCGAGCGCTCGCG-AGTCCCTGCCGTGTCCCCG
- Melan       GCTACTCCAGCT-ACCACCTGCATGCAGCTGCACAGC
- Pseudo      GCCACTGAGACT-GCCACCTGCATGCAGCTGCACAGA

## Overview

- Local Alignment (CHAOS)
- Multiple Global Alignment (LAGAN)
- 	-	Whole Genome Alignment
- Glocal Alignment (Shuffle-LAGAN)
- Biological Story

## Acknowledgments

- Stanford:
- Serafim Batzoglou
- Arend Sidow
- Matt Scott
- Gregory Cooper
- Chuong (Tom) Do
- Sanket Malde
- Kerrin Small
- Mukund Sundararajan

- Berkeley:
- Inna Dubchak
- Alexander Poliakov
- Göttingen:
- Burkhard Morgenstern
- Rat Genome Sequencing Consortium

- _http://lagan.stanford.edu/_