GIBBS SAMPLING
Presented by:
2019-ag-6001 Zainab Sheikh
2019-ag-6009 Mubeen Fatima
2019-ag-6045 Muhammad Umair
Submitted to:
Mam Sumaira Nishat
BS Bioinformatics (5th)
Department of Computer Science,
University of Agriculture
BRIEF HISTORY
Gibbs Sampling is named
after the physicist Josiah
Willard Gibbs, was an
American scientist.
The Algorithm was
described by brothers
Stuart Geman and
Donald Geman in 1984,
some eight decades after
the Death of Gibbs.
STATISTICAL ORIGIN
Gibbs sampling is commonly used for statistical
inference (i.e., determining the best value of a
parameter)
such as determining
the number of people
likely to shop at a
particular store on a
given day
the candidate a voter
will most likely vote Local optima (local max and min) and Global
for, etc. optima (global max and min)
INTRODUCTION
MSA and Motif Discovery are NP Hard i.e., For
fundamentals of bioinformatics
Computational discovery of TFBS- Transcription
Factor Binding Sites
Matrix optimization method
Optimal pattern (local optima, global optima)
Local Alignment
Iterative Approach
WORKFLOW
Why In Bioinformatics?
Gibbs Sampling is used To
find Motifs in Divergent
Unaligned sequences.
What is MOTIF?
Why for Distantly Related
Sequences?
What is MOTIF?
A motif is a short conserved sequence pattern
A distinct structural site performing a particular function
Of approximate length i.e. Zinc-finger motif has a length
of 10-20 amino acids.
Why for Distantly Related
Sequences?
For a set of closely related sequences, commonly shared
motifs can be discovered by MSA.
Distantly related sequences that share common motifs
cannot be readily aligned
For detecting subtle motifs between divergent sequences
(infinity or limit of sequence doesn’t exist) ,more
sophisticated algorithms such as EM and Gibbs Sampling
are used.
Gibbs Sampling approach is more versatile to detect
weakly conserved patterns.
ADVANTAGES
More flexible than EM (Expectation Maximization)
It uses more weighted functions unlike EM that uses
PSSM
Microarray
Phylogenetic foot-printing
(weakly conserved motif detection)
Expression Profiling
(structure prediction of secondary RNA)
LIMITATIONS VS IMPROVEMENTS
MD with enhanced To reduce local optima
resistance to local trapping we use
optima GibbsST- Gibbs
Stimulating Tempering
Long convergence of
(a thermodynamic
time
approach)
ALGORITHM
TOOLS IN BIOINFORMATICS
1. Gibbs Sampler
2. AlignACE
3. Melina (Motif Elucidator In Nucleotide sequence Assembly)
Gibbs Sampler
Web based program that uses the Gibbs Sampling approach
to look for short , partially conserved segments
Both for DNA or protein segments.
AlignACE
◦ Web-based program using the Gibbs sampling algorithm to find common motifs.
◦ The program is optimized for DNA sequence motif extraction.
◦ It automatically determines the optimal number and lengths of motifs from the
input sequences.
MELINA
(Motif Elucidator In Nucleotide sequence Assembly)
◦ Web-based program that runs four individual motif-finding algorithms – MEME, GIBBS
sampling, CONSENSUS, and Coresearch – simultaneously.
◦ The user compares the results to determine the consensus of motifs predicted by all four
prediction methods.
ALHAMDULILLAH !
َاْل ُد هّٰلِل
َحْم
