# Presentation: 478174

## The Identification

**Of**
**Complete Protein Domains **
**With**
**Accurate E-values**

**Bldg. 38A, Rm. 6N 603**
**NCBI, NLM, NIH**
**Bethesda MD 20894**

**spouge@ncbi.nlm.nih.gov**

**John L. Spouge**
**National Center for Biotechnology Information**
**NLM, NIH, DHHS**

## The NCBI Conserved Domain Database (CDD)
Multiple Sequence Alignment
Block & Spacer Data Structure
Alignment
Alignment Graphs
Position-Specific Scoring Matrices
Types of Alignment: Local, Semi-global, Global
Programs for aligning domains to query proteins
Reverse Position-Specific BLAST (RPS-BLAST)
Hidden Markov Models (HMMs)
GLOBAL
specifically respects the block structure in CDD.
has a accurate statistics (E-value).
is capable of heuristic acceleration like RPS-BLAST.

**Multiple Sequence Alignment**
**Block & Spacer Data Structure**
**Alignment**
**Alignment Graphs**
**Position-Specific Scoring Matrices**
**Types of Alignment: Local, Semi-global, Global**
**Programs for aligning domains to query proteins**
**Reverse Position-Specific BLAST (RPS-BLAST)**
**Hidden Markov Models (HMMs)**
**GLOBAL**
**specifically respects the block structure in CDD.**
**has a accurate statistics (E-value).**
**is capable of heuristic acceleration like RPS-BLAST.**

- Overview

## The Block Data Structurein theConserved Domain Database(CDD)

**L Geer *****et al *****(2002) *****Genome Res *****12:1619**

## Protein Sequence ConservationOccurs in Blocks with Intervening Spacers

**Protein Structure Alignment**

******-helix**

******-strand**

**loops**

**red sequence**

**blue sequence**

**Subsequences **
**corresponding to **
**secondary structure elements **
**(********-helices and ********-strands) **
**are more conserved than **
**the intervening loops.**

## The Conserved Domain Database

**are the building blocks in molecular evolution. **
**are recombined to make proteins with different functions.**
**The Conserved Domain Database (CDD)**
**is a collection of multiple sequence alignments (MSAs) representing conserved domains. **
**is linked to 3-dimensional structures in the PDB.**

**RPS-BLAST is the current default tool for CDD retrieval.**

**Notes:**
The conserved domain database, also maintained from the NCBI’s structure group, is a collections of domain multiple alignments linked to the protein 3D structure.

## The Curated Block Data Structure in the CDD

**protein**
**sequences**

**“****curated**
**blocks”**

**curated**
**alignment**

**end-gap**

**curated spacer**

**curated spacer**

**end-gap**

**“****CD footprint”**

**curated**
**blocks**

**Alignments in curated spacers are adventitious.**

**Curated blocks contain no gap characters.**

## Blocks and Spacers

** **

**curated block**

**curated spacer**

**block**

**spacer**

**Add columns with fewer than 50% gap characters.**

**Domain 1 Hemoglobin**

**Notes:**
The Multiple sequence alignment of all the sequences belonging to this domain will be given, and functional features marked. Thus CDD, combines protein and structure information, and uses their conservation patterns across evolution to provide useful functional annotation.

## A Sequence AlignmentCanBe Representedasa Directed Planar Graph

## Each Global Sequence Alignment Corresponds to a Path in a Graph

- T

- O

**Global alignment aligns whole sequences.**

## An Alignment Graph is a Directed Lattice Graph

- O

- ACDEFGUVWXNPQY

- ACDUVEFGWXYNPQ

- An Alignment Graph is a Directed Lattice Graph

**An alignment graph is a planar lattice graph. **
**Into each point P come:**
**eastward and northward arcs, having arbitrary length, and **
**one northeastward edge.**

## A Multiple AlignmentGeneratesA Position-Specific Scoring Matrix(PSSM)

## A Multiple Sequence Alignment Yields a Count Matrix

**“****count”**
**n-th amino acid**
**j-th column**

- A Multiple Sequence Alignment Yields a Count Matrix

## A Count Matrix Yields a Position-Specific Scoring Matrix (PSSM)

- A Count Matrix Yields a Position-Specific Scoring Matrix (PSSM)

**R Tatusov *****et al *****(1994) *****PNAS *****91:12091**

## A Position-Specific Scoring Matrix (PSSM) Yields an Alignment Matrix

## A Query Sequence and an Alignment MatrixYield an Alignment Graph

**A northeastward edge**
**has a weight**
**corresponding to the**
**entry in the alignment**
**matrix.**

## TerminologyforThree Types of Sequence Alignments

## Three Types of Alignments

**Local**
**      ****Alignment      **

**Subsequence**
**To**
**Subsequence**

**Semi-Global**
**Alignment**

**Subsequence**
**Onto**
**Sequence**

**Global**
**Alignment**

**Sequence**
**To**
**Sequence**

**BW Erickson & P Sellars***** *****(1983) **_**Time Warps, String Edits, and Macromolecules**_**,***** *****p. 55**

**Glocal**
**Alignment**

**gap**

**gap**

## E-values in Database Retrieval

## BLAST E-values

**SF Altschul *****et al *****(1997) *****Nucl Acids Res *****25:3389**

**hereditary non-polyposis colon cancer**
**hits to**
**DNA mismatch repair proteins **

**The E-value estimates the expected number of unrelated sequences in the database with such a high sequence similarity.**

**A Lindblom *****et al***** (1993) *****Nat Genet***** 5:279**

## The Retrieval of DomainsFromThe Conserved Domain Database(CDD)

## When searching proteins for complete domains, semi-global alignment is the method of choice.
Semi-global alignment methods align subsequences within a query protein to a complete domain.
Local alignment methods only align subsequences within a query protein to a piece of a domain.
They do not define domain boundaries.
They can be fooled by strong but incomplete matches.
An accurate E-value helps naïve CDD users.
CDD retrieval tools should be fast.
High-throughput retrieval applications require speed, e.g., transferring CDD annotation to newly discovered genes. 
HMMs have no intrinsic heuristics to speed computation.
The word-match heuristics accelerating RPS-BLAST are available to any tool using gapless alignment to align the CD blocks to sequences.

**Semi-global alignment methods align subsequences within a query protein to a complete domain.**
**Local alignment methods only align subsequences within a query protein to a piece of a domain.**
**They do not define domain boundaries.**
**They can be fooled by strong but incomplete matches.**
**An accurate E-value helps naïve CDD users.**
**CDD retrieval tools should be fast.**
**High-throughput retrieval applications require speed, e.g., transferring CDD annotation to newly discovered genes. **
**HMMs have no intrinsic heuristics to speed computation.**
**The word-match heuristics accelerating RPS-BLAST are available to any tool using gapless alignment to align the CD blocks to sequences.**

- Ideal CDD Retrieval

## Conserved Domain Database (CDD)Retrieval Tools

## Local Alignment Tools
match subsequences within a query protein to pieces of a domain. 
Reverse Position-Specific BLAST (RPS-BLAST)
HMMer_local

Semi-global Alignment Tools
match subsequences within a query protein to a complete domain.
HMMer_semi-global
GLOBAL

**match subsequences within a query protein to pieces of a domain. **
**Reverse Position-Specific BLAST (RPS-BLAST)**
**HMMer_local**
**Semi-global Alignment Tools**
**match subsequences within a query protein to a complete domain.**
**HMMer_semi-global**
**GLOBAL**

- Conserved Domain Database (CDD)Retrieval Tools

**ftp://ftp.genetics.wustl.edu/pub/eddy/hmmer/CURRENT/Userguide.pdf**

## Reverse Position-Specific BLAST(RPS-BLAST)

- Reverse Position-Specific BLAST(RPS-BLAST)

**block**

**block**

**RPS-BLAST does not respect blocks at all.**

**“****I don’t get no respect!”**

**A Schaffer *****et al *****(1999) *****Bioinformatics *****15:1000**

**query sequence**

**local**
**alignment**

**alignment graph**

**block**

**Comedian**
**Rodney Dangerfield**

**11/1 affine**
**gap penalty**

**Spacers are omitted.**

## Reverse Position-Specific BLAST(RPS-BLAST)

**RPS-BLAST aligns queries locally.**

## An IntroductiontoHidden Markov Models

## Hidden Markov Models(HMMs)

- Hidden Markov Models(HMMs)

**R Durbin *****et al. *****(1998) **_**Biological Sequence Analysis**_

**Hidden Markov States are unobservable.**

**Emitted symbols are observable.**

**transition probabilities**

**Alphabet of Emitted Symbols**
**ACDEFGHIKLMNPQRSTVWY**

**transition**

**Y**

**D**

**N**

**A**

**I**

**H**

**emission probabilities**

**HIANDY**

**loop transition**

## Hidden Markov Models Can Align Sequences

**R Durbin *****et al. *****(1998) **_**Biological Sequence Analysis**_

**HMMs can estimate their transition and emission**
**probabilities from examples of generated strings.**

**The hidden states most likely to generate a given string can be determined.**

**HMMs can align sequences.**

## HMMer

**ftp://ftp.genetics.wustl.edu/pub/eddy/hmmer/CURRENT/Userguide.pdf**

## Hidden Markov Models(HMMer)

**or CD footprint.**

- Hidden Markov Models(HMMer)

**HMMer is trained on the CDD**
**sequences.**

## Hidden Markov Models(HMMer_local)

- Hidden Markov Models(HMMer_local)

**HMMer_local aligns a free module to sequences.**

## Hidden Markov Models(HMMer_semi-global)

- Hidden Markov Models(HMMer_semi-global)

**HMMer_semi-global aligns a fixed module to sequences.**

## GLOBAL(Global Blocks Aligned Locally)A Semi-global Alignment Tool for QueryingA Database of Domains

## GLOBALGLObal Blocks Aligned Locally

- GLOBALGLObal Blocks Aligned Locally

**GLOBAL assigns score 0 to unaligned sequence or block ends.**

**local**
**alignment**

**local**
**alignment**

**local**
**alignment**

**GLOBAL aligns blocks with ungapped local alignments.**

**“****GLOBAL gives blocks**
**the respect they deserve!”**

## GLOBALGLObal Blocks Aligned Locally

- GLOBALGLObal Blocks Aligned Locally

**GLOBAL aligns queries semi-globally.**

## GLOBALGLObal Blocks Aligned Locally

- GLOBALGLObal Blocks Aligned Locally

**local**
**alignment**

**local**
**alignment**

**Problem: GLOBAL aligns one sub-block per block.**

**Solution: Split excessively long blocks.**

## The GLOBAL Alignment Algorithm

**GLOBAL Alignment Graph**

- O

- T

## GLOBAL as a Special Hidden Markov Model (HMM)

- GLOBAL as a Special Hidden Markov Model (HMM)

## GLOBAL as a Special Hidden Markov Model (HMM)

- GLOBAL as a Special Hidden Markov Model (HMM)

**The alignment graph**
**for one block**

**The HMM**
**for one block**

**The GLOBAL HMM**
** ****emission probabilities**
**are fit to data.**

**The GLOBAL HMM**
**transition probabilities**
**are predetermined.**

- Path-Invariance

## A Standard of TruthForthe EvaluationOfCDD Retrieval

## The Structural Database DB_10185(DB_Structure)

- The Structural Database DB_10185**(**DB_Structure)

**Structural Protein Database PDB**

**Single-linkage clustering with BLAST E-value less than 10****-80**

**DB_Structure is a set of non-redundant protein structures from PDB.**

**protein structure**

**E-value**
**less than 10****-80**

**the representative**
**from a cluster**

**http://www.ncbi.nlm.nih.gov/Structure/VAST/nrpdb.html**

## The Structural Database DB_Structure

## The Structural CD Database DB_331_CD (DB_MSA_Structure)

- The Structural CD Database DB_331_CD (DB_MSA_Structure)

**Conserved Domain Database CDD**

**The CDD is structured as a hierarchy of MSAs.**

**CDD parent**

**manually **
**curated**

**MSA contains**
**a sequence**
**with structure**
**in  PDB**

**http://www.ncbi.nlm.nih.gov/Structure/cdd/cdd.shtml**

## The Structural CD Database DB_MSA_Structure

**ftp://ftp.ncbi.nih.gov/pub/GLOBAL**

**DB_MSA_Structure is a set of CD MSAs with at least one structure.**

## DB_Structure and DB_MSA_Structure

**DB_Structure is a set of non-redundant protein structures from PDB.**

**http://www.ncbi.nlm.nih.gov/Structure/VAST/vast.shtml**

**DB_MSA_Structure is a set of CD MSAs with at least one structure.**

**The structure “contains” the**
**MSA domain if VAST footprint occupies 80% of CD footprint.**

**VAST footprint.**

## CDD Retrieval Performance

## The ROCn Plot Measures Retrieval Performance

**semi-global**

**local**

- The ROCn Plot Measures Retrieval Performance

**RPS-BLAST**

**HMMer_local**

**HMMer_semi-global**

**GLOBAL**

**Semi-global methods**
**dominate local methods**
**in domain retrieval.**

**M Gribskov & NL Robinson***** *****(1996) *****Computers in Chemistry *****20:25**

## Why Retrieve DomainsWith  GLOBAL Instead ofWith HMMer_semi-global?

## GLOBAL Can Have Heuristics and An Accurate E-value

**The word-match heuristics in RPS-BLAST can accelerate GLOBAL.**

**GLOBAL has an accurate E-value.**

## Errors per Query

## EPQ PlotEmpirical Errors per Query vs. E-value

- EPQ PlotEmpirical Errors per Query vs. E-value

**RPS-BLAST**

**HMMer_local**

**HMMer_semi-global**

**GLOBAL**

**The standard of truth**
**misses about 2% of the**
**domain relationships.**

## Theoretical EvaluationOfThe E-values

- Theoretical EvaluationOfThe E-values

## The Random Model of Independent Letters

**Robinson AB & Robinson LR (1991) PNAS 88:8880**

**One-Letter Code for Amino Acid Alphabet (L = 20)**
**ACDEFGHIKLMNPQRSTVWY**

## HMMer’sE-values are Inaccurate Approximations

- HMMer’sE-values are Inaccurate Approximations

**Y-K Yu***** et al. *****(2002) Bioinformatics 18**:864

**HMMer fits its Gumbel approximation’s parameters ******** and *****k***
**to simulated sequences with a Gaussian length distribution**
**with mean 350.**

## Three Sample CDs

**cd00030**
**Protein kinase C conserved region 2 (CalB)**
**Ca2+ binding**

**cd00083**
**Helix-loop-helix domain**
**DNA binding in some transcription factors**

**cd00288**
**Pyruvate kinase**

## Three Sample CDs

**44 blocks**
**lengths **
**13, 5, 10, 10, 21, 13, 8, 8, 10, 6, 6, 10 ,7, 15, 8, 7, 7, 10, 7, 6, 8, 17, 12, 8, 6, 6, 9, 19, 8, 12, 14, 8, 8, 17, 17, 18, 11, 10, 12, 10, 13, 19, 18, and 13**** **

**cd00030**
**8 blocks**
**lengths **
**16, 16, 12, 6, 11, 15, 17, and 12**** **

**cd00083**
**2 blocks **
**lengths **
**34 and 26**** **

## HMMer’sE-values are Inaccurate Approximations

- HMMer’sE-values are Inaccurate Approximations

**HMMer fits its Gumbel approximation’s parameters ******** and *****k***
**to simulated sequences with a Gaussian length distribution**
**with mean 350.**

**cd00288**

**cd00083**

**E = 0.1**

**E = Np**

**N = 331 CDs**

**cd00030**

**L = 350**

**twilight zone**

## GLOBAL’s E-values are Accurate Approximations

- GLOBAL’s E-values are Accurate Approximations

**GLOBAL fits its distribution with **
**the independent alignments approximation.**

**cd00288**

**cd00083**

**cd00030**

**E = 0.1**

## The GLOBAL E-value

## The Independent Alignments Approximation

- “The Little Mermaid Insight”

## The Independent Alignments Approximation

**Independent Alignments with Same Distribution for Maximum Sum **

## The Independent Alignments Approximation

**“****effective length”**

## The Independent Alignments Approximation

**The number of ways of choosing the starting points in the right order**

**The number of ways**
**of choosing**
**b of n objects.**

## The Independent Alignments Approximation

**The number of ways of choosing the starting points without concern for order**

## The Independent Alignments Approximation

**The independent alignments approximation is **_**asymptotically**_** correct for local alignments.**

**The probability approximation has been changed into the problem of a combinatorial match.**

## Why Are Asymptotics Important?

**What can possibly go wrong???**

**GLOBAL tail probability**

**The GLOBAL tail is**
**asymptotically a straight line.**

**The GLOBAL score is a maximum of**
**non-negative quantities.**

## What can possibly go wrong???

**What can possibly go wrong???**

## Combinatorial Matchesfor Different Types of Block Alignments

- Combinatorial Matchesfor Different Types of Block Alignments

**query sequence**

**GLOBAL aligns blocks with gapless local alignment.**

**G-SALTO aligns blocks with gapless semi-global alignment.**

**“****threading combinatorics”**

**JL Spouge ***** et al. ***** (1999) *****Annals of Combinatorics *****3:81**

## Semi-global alignment tools (namely, HMMer_semi-global and GLOBAL) dominate local alignment tools (namely, HMMer_local and RPS-BLAST) when finding complete domains within protein sequences.
GLOBAL
has retrieval performance competitive with HMMer_semi-global.
HMM emission probabilities are likely more important than transition probabilities.
has an accurate E-value. 
Accurate E-values 
are important to naïve database users.
are necessary for iterative tools, e.g., PSI-BLAST.
is capable of heuristic acceleration like RPS-BLAST.
is being implemented for CDD retrieval at NCBI.

**Semi-global alignment tools (namely, HMMer_semi-global and GLOBAL) dominate local alignment tools (namely, HMMer_local and RPS-BLAST) when finding **_**complete**_** domains within protein sequences.**
**GLOBAL**
**has retrieval performance competitive with HMMer_semi-global.**
**HMM emission probabilities are likely more important than transition probabilities.**
**has an accurate E-value. **
**Accurate E-values **
**are important to naïve database users.**
**are necessary for iterative tools, e.g., PSI-BLAST.**
**is capable of heuristic acceleration like RPS-BLAST.**
**is being implemented for CDD retrieval at NCBI.**

## Acknowledgements

**Chris Lanczycki and Charlie Liu: CDD PSSMs**
**Aron Marchler-Bauer: PDB**
**Andy Neuwald, Stephen Altschul, and Yi-Kuo Yu**

##  Maricel Kann

**Sergey Sheetlin**
**Yonil Park**
**Stephen H. Bryant**
**John L. Spouge**
**National Center for Biotechnology Information**

- Co-Authors on the GLOBAL Article

## Slide 72

## Slide 73