Basic Local Alignment Search Tool - PPTs

BLAST

1. BLAST, Mega BLAST, MUMmer and
AVID

2. What is BLAST?
BasicLocalAlignmentSearchTool
Itallowsrapidsequencecomparisonofaquery
sequenceagainstadatabase.
The BLAST algorithm is fast, accurate, and web-
accessible.
Developed in 1990 and 1997 (S. Altschul)

3. Why uses BLAST?
BLAST searching is fundamental to understanding the
relatedness of any favorite query sequence to other
known proteins or DNA sequences.
Applications include:-
Identifying orthologs and paralogs
Discovering new genes or proteins
Discovering variants of genes or proteins
Investigating expressed sequence tags (ESTs)
Exploring protein structure and function

4. Four Essential Components of BLAST
(1) Choose the sequence (query)
(2) Select the BLAST program
(3) Choose the database to search
(4) Choose optional parameters
Then click “BLAST”

5. BLAST ACCESS
NCBI BLAST
http://www.ncbi.nlm.nih.gov/BLAST/
Canadian Bioinformatics Resource BLAST
http://cbr-rbc.nrc-cnrc.gc.ca/blast/
European Bioinformatics Institute BLAST
http://www.ebi.ac.uk/blastall/
http://www.ebi.ac.uk/blast2/

6. NCBI BLAST

7. Canadian Bioinformatics Resource BLAST

8. European Bioinformatics Institute BLAST

9. Input Format
Inputsequencesarein:-
FASTAformator
Genbankformat.

10. 1. Nucleotide BLAST
BLAST
N–Nucleotide BLAST
Searchanucleotidedatabaseusing
anucleotidequery

11. Input Page

12. 2. Protein BLAST
BLAST
P–Protein BLAST
Search proteindatabase using
aproteinquery

13. Input Page

14. 3. BLASTX –Translated BLAST
Searchproteindatabase using atranslated
nucleotidequery

15. Input Page

16. 4. tBLAST
N
Searchtranslatednucleotidedatabaseusing
aproteinquery

17. Input Page

18. 5. tBLAST
X
Searchtranslatednucleotidedatabaseusing
atranslatednucleotidequery

19. Input Page

20. What is Genomic BLAST?
GenomicBLAST,anovelgraphicaltoolfor
simplifyingBLASTsearchesagainstcomplete
andunfinishedgenomesequences.
Thistoolallowstheusertocomparethe
querysequenceagainstavirtualdatabaseof
DNAand/orproteinsequencesfroma
selectedgroupoforganismswithfinishedor
unfinishedgenomes.

21. What is Genomic BLAST?
Currentlyprovidesaccesstoover
170bacterialandarchaealgenomesand
over40eukaryoticgenomes.

22. Specialized BLAST
PrimerBLAST–FindingPrimer
CDSBLAST-Conserveddomainsequences
GEOBLAST-Geneexpressiondata
IgBLAST–Immunoglobulinsequences
SNPBLAST–Singlenucleotidepolymorphismetc.,

23. Primer BLAST -Input Page

24. CDS BLAST -Input Page

25. GEO BLAST -Input Page

26. Ig BLAST -Input Page

27. SNP BLAST -Input Page

28. Advanced BLAST
PSIBLAST–PositionSpecificIterativeBLAST
PHIBLAST–PatternHitIterativeBLAST
ThesetwoBLASTProgramsarecalled“Iterative
BLAST”

29. PSI BLAST
Position-SpecificIterated(PSI)-BLASTisthe
mostsensitiveBLASTprogram,makingit
usefulforfindingverydistantlyrelated
proteinsornewmembersofaproteinfamily.

30. PHI BLAST
Pattern-HitInitiated(PHI)-BLASTisdesignedto
searchforproteinsthatcontainapatternspecified
bytheuserANDaresimilartothequerysequence
inthevicinityofthepattern.
Thisdualrequirementisintendedtoreducethe
numberofdatabasehitsthatcontainthepattern,
butarelikelytohavenotruehomologytothe
query.

31. BLAST2
ItutilizestheBLASTalgorithmforpairwiseDNA-
DNAorprotein-proteinsequencecomparison.
Ithasbeenveryusefulforthecomparisonof
homologousgenesfromcompletemicrobial
genomes.
BLAST2.0algorithmgeneratesagappedalignment
byusingdynamicprogramming.

32. BLAST2
SEGandDUSTProgramsareusedtoremovethe
low-complexityregions.
Theprogramisnotgenerallyusefulformotif-style
searchingandaligningmegabasesizegenomic
sequencesisnotrecommended.
Themaximumnumberofcharacterspersequence,
thatmaybeaccommodatedis~150kb,the
optimalsizeofquerysequenceisabout1kb.

33. Output Page

34. MEGA BLAST
ComparisonoflargesetsoflongDNAsequences.
It'smuchfasterthanthestandardBLASTN
ItusesthegreedyalgorithmofWebbMilleretal.for
nucleotidesequencealignmentsearch
Itisuptotentimesfasterthanmorecommonsequence
similarityprogramsandthereforecanbeusedtoquickly
comparetwolargesetsofsequencesagainsteachother.

35. Suffix tree
Suffixtree,asthenamesuggestsisa
treeinwhicheverysuffixofastringSis
represented.
More formally defined, suffix tree is an
automaton which accepts every suffix
of a string.

36. Suffix tree
Exampleofsuffixtreeforthestring
“ABC”
1,2and3representtheendsof
suffixesstartingatpositions1,2
and3respectively.Thesearethe
leafnodes.

37. MUMmer –Genome alignment
algorithm
Developed by
Dr. Steven Salzberg’s group at TIGR
NAR (1999) 27:2369-2376
NAR (2002) 30:2478-2483
Availability
Free
TIGR (The Institute of Genomic Research) site

38. Features
The algorithm assumes that sequences are closely related
Can quickly compare millions of bases
Outputs:
Base to base alignment
Highlights the exact matches and differences in the
genomes
Locates
SNPs
Large inserts
Significant repeats
Tandem repeats and reversals

39. Technique used in MUMmer algorithm
Compute Suffix trees for every genome
Longest Increasing Subsequence (LIS)
Alignment using Smith & Waterman algorithm
Integration of
these techniques
for genome alignment

40. Steps
Locating MUMs
Sorting MUMs
Closure with gaps
G1: ACTGATTACGTGAACTGGATCCA
G2: ACTCTAGGTGAAGTGATCCA

41. Genome1: ACTGATTACGTGAACTGGATCCA
Genome2: ACTCTAGGTGAAGTGATCCA
Genome1:ACTGATTACGTGAACTGGATCCA
Genome2:ACTCTAGGTGAAGTGATCCA
ACTGATTACGTGAACTGGATCCA
ACTC--TAGGTGAAGT-GATCCA

42. What is MUM?
MUMisasubsequencethatoccursexactlyoncein
bothgenomesandisNOTpartofanylonger
sequence
TwocharactersthatboundaMUMarealways
mismatches
GenA:tcgatcGACGATCGCCGCCGTAGATCGAATAACGAGAGAGCATAA cgactta
GenB:gcattaGACGATCGCCGCCGTAGATCGAATAACGAGAGAGCATAA tccagag
Similar to
BLAST & FASTA!!

43. Sorting & ordering MUMs
MUMs are sorted according to their position in
Genome A
The order of matching MUMs in Genome B is
considered
LIS algorithm to locate longest set of MUMs which
occur in ascending order in both genomes
2
4
MUM5:
transposition
MUM3:
Random match
Inexact repeat
Leads to Global MUM-alignment

44. Results: Alignment of M. tuberculosis strains
CDC1551 (Top) & H37Rv (bottom)
Single green lines
indicate SNPs
Blue lines
indicate insertions

45. Comparison of 2 Mycoplasma genomes
cousins that are distantly related
M. genitalium: 580 074 nt
M. pneumoniae: 816 394 (+226 000)
Analysis of proteins tell us that all M.g. proteins are
present in P.m.
Alignment was carried using
FASTA (dividing each genome into 1000 bp)
All-against-all searches
Fixed length of pattern (25)
Using MUMmer (length = 25)

46. Comparison of 2 Mycoplasma genomes
Using FASTA
Fixed length
patterns: 25mers
MUMmer

47. AVID –Global alignment algorithm
Avidisdesignedtobefast,memoryefficient,and
practicalforsequencealignmentsoflargegenomic
regionsuptomegabaseslong.
AVIDgloballyalignsDNAsequencesofarbitrary
lengthforthepurposeofannotationandbiological
discoveryusingsyntenicgenomicsequencesfrom
twoorganisms.

48. Key features
Alignshundredsofkilobasesquickly
Highlyaccurateandabletodetectweak
homologies
Abletohandleonesequenceindraftbyordering
andorientingthecontigsautomatically

49. Key features
Fastalignmentofsimilarsequencesisusefulfor
alignmentsofprimatesequencesorcomparisonof
assemblies.
Itworksbyrecursivelyfindingstronganchorsfrom
thecollectionofmaximalmatchesinthe
sequences.