<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass{beamer}
\usepackage{breqn}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{setspace}

\usepackage{amssymb}


% Beamer theme
\usetheme{Madrid}
\usepackage{listings}
\usepackage{color}

% Define MATLAB code colors for the listings package
\definecolor{mygreen}{rgb}{0,0.6,0}
\definecolor{mygray}{rgb}{0.5,0.5,0.5}
\definecolor{mymauve}{rgb}{0.58,0,0.82}

% Custom settings for MATLAB code using listings
\lstset{
    language=Matlab,
    basicstyle=\ttfamily\small,       % Code font size and style
    keywordstyle=\color{blue},        % Keywords color
    commentstyle=\color{mygreen},     % Comment color
    stringstyle=\color{mymauve},      % String color
    numberstyle=\tiny\color{mygray},  % Line number color
    backgroundcolor=\color{white},    % Background color
    showstringspaces=false,           % Don't show spaces as underscores
    numbers=left,                     % Line numbers on the left
    stepnumber=1,                     % Line number step
    numbersep=5pt,                    % Distance of numbers from code
    frame=single,                     % Frame around the code
    rulecolor=\color{black},          % Frame border color
    breaklines=true,                  % Break long lines
    breakatwhitespace=false,          % Don't break at whitespace
    tabsize=4                         % Tab size
}

\AtBeginSection[]{
    \begin{frame}
        \centering
        \Huge \insertsection
    \end{frame}
}
\title{Patterns in Biological Sequences}
\author{Prof. Singh}
\date{}

\begin{document}

\frame{\titlepage}

\tableofcontents{}

\section{Introduction}
% Slide 1 - Patterns
\begin{frame}{Patterns}
    \begin{itemize}
        \item A pattern is an element that occurs multiple times in a given set of biological sequences.
        \item Patterns are mainly present in non-coding regions of DNA.
        \item Examples of patterns include:
        \begin{itemize}
            \item A+T or G+C regions
            \item Telomeric repeats of sequence AGGGTT
            \item TATA Box, CAAT Box, etc.
        \end{itemize}
    \end{itemize}
\end{frame}

% Slide 2 - Importance of Patterns
\begin{frame}{Importance of Patterns}
    \begin{itemize}
        \item Patterns provide information about the structure of proteins that DNA interacts with.
        \item Patterns in eukaryotic DNA may provide regulatory functions.
        \item Patterns represent functional control points for cell-specific or differential gene expression.
        \item Patterns such as splice sites or binding sites drive the detection of higher-level abstractions.
    \end{itemize}
\end{frame}

% Slide 3 - Sequence vs Pattern Modeling
\begin{frame}{Sequence vs Pattern Modeling}
    \begin{itemize}
        \item \textbf{Sequence Model}: A model of sequence characteristics that provides a basis for establishing the significance of observed patterns.
        \item \textbf{Pattern Model}: Codifies and looks for specific motifs of functional significance.
        \item Example: The probability of finding a TATA box â€œTATAATâ€ in A+T rich sequences is higher than in G+C rich sequences.
    \end{itemize}
\end{frame}


\section{Sequence Models}

% Slide 4 - Sequence Models
\begin{frame}{Sequence Models}
    \begin{itemize}
        \item Sequence models represent the random changes in a sequence caused by mutations or other factors.
        \item Two main types:
        \begin{itemize}
            \item Independent Identical Distribution (IID)
            \item Markov Chain (MC)
        \end{itemize}
    \end{itemize}
\end{frame}

% Slide 5 - IID Model
\begin{frame}{Independent Identical Distribution (IID)}
    \begin{itemize}
        \item Simplest sequence model where the probability of occurrence of a nucleotide is equal and independent.
        \item Each nucleotide has an equal chance of appearing, independent of others.
    \end{itemize}
\end{frame}

% Slide 6 - ML Estimation of IID Model
\begin{frame}{Maximum Likelihood Estimation of IID Model}
    \begin{itemize}
        \item For a sequence of length \( L \), the probability of each base \( \alpha \) is:
        \[
        P(\alpha) = \frac{n_\alpha}{L}
        \]
        \item Example: For a DNA sequence, the probability of observing a pattern is calculated by multiplying the probabilities of the individual bases.
    \end{itemize}
\end{frame}

% Slide 7 - IID Example
\begin{frame}{IID Example}
    \begin{itemize}
        \item Consider the following DNA sequence of length 25:
        \[
        \text{SEQ} = \text{AACGTCTCTATCATGCCAGGATCTG}
        \]
        \item Given the alphabet \( \Sigma = \{A, C, T, G\} \), the IID model parameters are:
        \[
        \left\{\frac{6}{25}, \frac{7}{25}, \frac{5}{25}, \frac{7}{25}\right\}
        \]
        \item The probability of finding the pattern CAAT in this sequence:
        \[
        P(CAAT) = \frac{7}{25} \times \frac{6}{25} \times \frac{6}{25} \times \frac{7}{25} = 0.0045
        \]
    \end{itemize}
\end{frame}

% Slide 8 - Markov Chain Model
\begin{frame}{Markov Chain Model}
    \begin{itemize}
        \item A Markov chain model implies that the current state (nucleotide) depends on previous states.
        \item For biological patterns, the probability of a nucleotide at position \( i \) depends on the nucleotide at position \( i-1 \).
    \end{itemize}
\end{frame}

% Slide 9 - Markov Chain Model Example
\begin{frame}{Markov Chain Model Example}
    \begin{itemize}
        \item Path through the model and probability \( P(\text{cggt}) \):
        \[
        P(\text{CGGT}) = P(\text{C}) \cdot P(\text{G} | \text{C}) \cdot P(\text{G} | \text{G}) \cdot P(\text{T} | \text{G})
        \]
        \item Transition probabilities are used to compute the sequence probability.
    \end{itemize}
\end{frame}

% Slide 10 - First Degree Markov Chain Model
\begin{frame}{First Degree Markov Chain Model}
    \begin{itemize}
        \item In a first-degree Markov chain model, the probability of observing a nucleotide at position \( i \) depends only on the nucleotide at position \( i-1 \).
        \item For higher-order models, the probability depends on more preceding positions.
    \end{itemize}
\end{frame}

% Slide 11 - Sequence Models Example

\begin{frame}{Sequence Models Example}
    \textbf{Example DNA Sequence:}
    \begin{itemize}
        \item Consider a 25-nucleotide sequence:
        \[
        \text{SEQ} = \text{AACGTCTCTATCATGCCAGGATCTG}
        \]
        \item This sequence can be modeled using a first-degree Markov chain by calculating the conditional probabilities between consecutive nucleotide pairs.
    \end{itemize}

    \textbf{Constructing a Transition Matrix:}
    \begin{itemize}
        \item We count dinucleotide pairs from the sequence:
        \begin{itemize}
            \item \( f_{AA} = 1, f_{AC} = 1, f_{AG} = 1, f_{AT} = 3, \dots \)
            \item Also note, \( f_A = f_{AA} + f_{AC} + f_{AG} + f_{AT} \)
        \end{itemize}
    \end{itemize}
\end{frame}
\begin{frame}{Contd ...}
        \begin{itemize}
        \item The frequencies are used to compute transition probabilities:
        \[
        P(A | A) = \frac{f_{AA}}{f_{AA} + f_{AC} + f_{AG} + f_{AT}} = \frac{f_{AA}}{f_A}, \quad P(C | A) = \frac{f_{AC}}{f_A}, \quad \dots
        \]
        \item These values fill the transition matrix:
        \[
        \begin{array}{c||c|c|c|c}
        &amp; A &amp; C &amp; G &amp; T \\
        \hline \hline
        A &amp; \frac{f_{AA}}{f_A} = \frac{1}{6} &amp; \frac{f_{AC}}{f_A} = \frac{1}{6} &amp; \frac{f_{AG}}{f_A} = \frac{1}{6} &amp; \frac{f_{AT}}{f_A}= \frac{3}{6} \\ \hline
        C &amp; \frac{f_{CA}}{f_C} = \frac{2}{7} &amp; \frac{f_{CC}}{f_C} = \frac{1}{7} &amp; \frac{f_{CG}}{f_C} = \frac{1}{7} &amp; \frac{f_{CT}}{f_C} = \frac{3}{7}\\ \hline
        G &amp; \frac{f_{GA}}{f_G} = \frac{1}{4} &amp; \frac{f_{GC}}{f_G} = \frac{1}{4} &amp; \frac{f_{GG}}{f_G} = \frac{1}{4} &amp; \frac{f_{GT}}{f_G} = \frac{1}{4} \\ \hline
        T &amp; \frac{f_{TA}}{f_T} = \frac{1}{7} &amp; \frac{f_{TC}}{f_T} = \frac{4}{7} &amp; \frac{f_{TG}}{f_T} = \frac{2}{7} &amp; \frac{f_{TT}}{f_T} = \frac{0}{7} \\ \hline
        \end{array}
        \]
    \end{itemize}

    \textbf{Example Calculation:}
    \begin{itemize}
        \item Probability of observing CAAT in the sequence:
        \[
        P(\text{CAAT}) = P(C) \cdot P(A | C) \cdot P(A | A) \cdot P(T | A)
        \]
        \[
        \text{Or,} \quad P(\text{CAAT}) = \frac{7}{24} \cdot \frac{2}{7} \cdot \frac{1}{6} \cdot \frac{3}{6} = 0.0069 \quad (\text{IID Prob} = 0.0045)
        \]
    \end{itemize}
\end{frame}


\section{Pattern Models}


% Slide 12 - Regular Expressions Search Engines
\begin{frame}{Regular Expressions Pattern Specification}
    \begin{itemize}
        \item Search engines using patterns or regular expressions can be adapted to find biological patterns.
         \item MATLAB supports the use of regular expressions for manipulating biological patterns.
        \item Example: \( TAT(AAT | TAT | AA) \) represents variations of the TATA box pattern.
        \item While these allow variations of occurrences, regular expressions do not enable the specification of a probability of occurrence of a specific character (base or amino acid) at a given location.
    \end{itemize}
\end{frame}


\section{Position-Specific Scoring Matrices (PSSM)}


% Slide 14 - 
\begin{frame}{Position-Specific Scoring Matrices (PSSM)}
    \begin{itemize}
        \item A PSSM represents the frequency of occurrence of each nucleotide in a sequence.
        \item Steps in constructing a PSSM:
        \begin{enumerate}
            \item Align sequences.
            \item Compute nucleotide frequencies.
            \item Calculate log-likelihood ratios.
        \end{enumerate}
    \end{itemize}
\end{frame}

\begin{frame}{Position-Specific Scoring Matrices (PSSM)}
    \textbf{Introduction to PSSM:}
    \begin{itemize}
        \item A Position-Specific Scoring Matrix (PSSM) is a table that represents the frequency or probability of each nucleotide (or amino acid) occurring at each position in a set of aligned sequences.
        \item PSSMs are widely used in bioinformatics to find conserved regions in sequences, such as DNA binding motifs.
    \end{itemize}
\end{frame}
\begin{frame}{Steps to Build a PSSM:}
    \begin{enumerate}
        \item \textbf{Multiple Sequence Alignment}: Align multiple sequences to identify conserved positions.
        \item \textbf{Frequency Calculation}: For each position in the alignment, calculate the frequency of each nucleotide (or amino acid).
        \item \textbf{Background Frequencies}: Estimate the background probability for each nucleotide (usually \(0.25\) for DNA bases A, C, G, T).
        \item \textbf{Log-Likelihood Calculation}: For each position and nucleotide, calculate the log-likelihood ratio using the formula:
        \[
        \text{PSSM score}(i, x) = \log_2 \left( \frac{P(x_i)}{P_{\text{bg}}(x)} \right)
        \]
        where \( P(x_i) \) is the observed frequency of nucleotide \( x \) at position \( i \) and \( P_{\text{bg}}(x) \) is the background probability of \( x \).
    \end{enumerate}
\end{frame}

\begin{frame}{PSSM Example}
    \textbf{Example: Aligned Sequences:}
    \begin{itemize}
        \item Consider the following aligned DNA sequences:
        \[
        \begin{array}{cccccc}
        A &amp; A &amp; C &amp; T &amp; T &amp; A \\
        A &amp; A &amp; T &amp; T &amp; T &amp; C \\
        A &amp; T &amp; T &amp; T &amp; A &amp; A \\
        C &amp; A &amp; A &amp; A &amp; A &amp; A \\
        A &amp; T &amp; A &amp; A &amp; G &amp; A \\
        A &amp; T &amp; G &amp; A &amp; A &amp; T
        \end{array}
        \]
    \end{itemize}

    \textbf{Step 1: Frequency Calculation:}
    \begin{itemize}
        \item Calculate the frequency of each nucleotide at each position:
        \[
        \begin{array}{c|cccccc}
        \text{Nucleotide} &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\
        \hline
        A &amp; 5/6 &amp; 3/6 &amp; 2/6 &amp; 3/6 &amp; 3/6 &amp; 4/6 \\
        C &amp; 1/6 &amp; 0/6 &amp; 1/6 &amp; 0/6 &amp; 0/6 &amp; 1/6 \\
        G &amp; 0/6 &amp; 0/6 &amp; 1/6 &amp; 0/6 &amp; 1/6 &amp; 0/6 \\
        T &amp; 0/6 &amp; 3/6 &amp; 2/6 &amp; 3/6 &amp; 2/6 &amp; 1/6 \\
        \end{array}
        \]
    \end{itemize}
\end{frame}

\begin{frame}{PSSM Example (Cont.)}
    \textbf{Step 2: Background Frequencies:}
    \begin{itemize}
        \item Assume equal background probabilities for each nucleotide \( P_{\text{bg}}(A) = P_{\text{bg}}(C) = P_{\text{bg}}(G) = P_{\text{bg}}(T) = 0.25 \).
    \end{itemize}

    \textbf{Step 3: Log-Likelihood Ratios:}
    \begin{itemize}
        \item Calculate the log-likelihood ratios for each nucleotide at each position. For example:
        \[
        \text{PSSM score}(1, A) = \log_2 \left( \frac{5/6}{1/4} \right) = \log_2(3.33) = 1.737
        \]
        \item The PSSM scores for position 1 would be:
        \[
        \begin{array}{c|c}
        \text{Nucleotide} &amp; \text{PSSM Score (Position 1)} \\
        \hline
        A &amp; 1.737 \\
        C &amp; \log_2\left(\frac{1/6}{1/4}\right) = -1.322 \\
        G &amp; \log_2\left(\frac{0}{1/4}\right) = -\infty \\
        T &amp; \log_2\left(\frac{0}{1/4}\right) = -\infty \\
        \end{array}
        \]
    \end{itemize}

    \textbf{Step 4: Complete PSSM:}
    \begin{itemize}
        \item Repeat the log-likelihood calculations for all positions and nucleotides to construct the full PSSM.
    \end{itemize}
\end{frame}

\begin{frame}{Applying the PSSM}
    \textbf{Using the PSSM to Score a Sequence:}
    \begin{itemize}
        \item To apply the PSSM to a new DNA sequence, slide the matrix across the sequence and sum the log-likelihood scores for each nucleotide at each position.
        \item Example: Applying the PSSM to the sequence \( GATTAC \):
        \[
        \text{Score} = \text{PSSM}(1, G) + \text{PSSM}(2, A) + \text{PSSM}(3, T) + \dots
        \]
    \end{itemize}

    \textbf{Interpreting the Scores:}
    \begin{itemize}
        \item The total score indicates how well the sequence matches the PSSM.
        \item Higher scores indicate better matches, while lower or negative scores indicate poor matches.
    \end{itemize}
\end{frame}

\begin{frame}{Avoiding Zero Probability with Laplace Rule in PSSM}
    \textbf{Laplace's Rule (Pseudocounts):}
    \begin{itemize}
        \item When constructing a PSSM, a zero frequency for a nucleotide at any position can lead to a log-likelihood of \( -\infty \).
        \item To avoid zero probabilities, Laplace's rule adds a small pseudocount (typically 1) to all observed counts.
        \item This adjustment ensures that no frequency is zero, which prevents log-likelihood scores from being undefined.
    \end{itemize}
    
    \textbf{Formula with Pseudocounts:}
    \begin{itemize}
        \item If \( n_x \) is the observed count of nucleotide \( x \) at a position, the pseudocount-adjusted frequency is:
        \[
        P(x) = \frac{n_x + 1}{N + | \Sigma |}
        \]
        where \( N \) is the total number of sequences and \( | \Sigma | \) is the alphabet size (4 for DNA: A, C, G, T).
    \end{itemize}
\end{frame}

\begin{frame}{PSSM Example with Laplace's Rule}
    \textbf{Example: Aligned Sequences:}
    \begin{itemize}
        \item Consider the following aligned DNA sequences:
        \[
        \begin{array}{cccccc}
        A &amp; A &amp; C &amp; T &amp; T &amp; A \\
        A &amp; A &amp; T &amp; T &amp; T &amp; C \\
        A &amp; T &amp; T &amp; T &amp; A &amp; A \\
        C &amp; A &amp; A &amp; A &amp; A &amp; A \\
        A &amp; T &amp; A &amp; A &amp; G &amp; A \\
        A &amp; T &amp; G &amp; A &amp; A &amp; T
        \end{array}
        \]
        \item Calculate frequencies at position 1 using Laplaceâ€™s rule:
        \[
        \begin{array}{c|c}
        \text{Nucleotide} &amp; \text{Raw Count} \\
        \hline
        A &amp; 5 \\
        C &amp; 1 \\
        G &amp; 0 \\
        T &amp; 0 \\
        \end{array}
        \]
    \end{itemize}

    \textbf{Step 1: Apply Laplace's Rule:}
    \begin{itemize}
        \item Adjusted counts with pseudocounts:
        \[
        \begin{array}{c|c}
        \text{Nucleotide} &amp; \text{Adjusted Count} \\
        \hline
        A &amp; 5 + 1 = 6 \\
        C &amp; 1 + 1 = 2 \\
        G &amp; 0 + 1 = 1 \\
        T &amp; 0 + 1 = 1 \\
        \end{array}
        \]
    \end{itemize}
\end{frame}

\begin{frame}{PSSM Example with Laplace's Rule (Continued)}
    \textbf{Step 2: Calculate Adjusted Probabilities:}
    Total number of sequences plus pseudocount adjustment: \( N + 4 = 6 + 4 = 10 \), yeilds adjusted probabilities for each nucleotide at position 1:
        \[\begin{array}{ll}
        P(A) = \frac{6}{10} = 0.6, \quad P(C) = \frac{2}{10} = 0.2, \\
        P(G) = \frac{1}{10} = 0.1, \quad P(T) = \frac{1}{10} = 0.1
        \end{array} \]

    \textbf{Step 3: Calculate Log-Likelihood Ratios (LLR) using a background frequency of \( P_{\text{bg}}(x) = 0.25 \)}:
          
        \[
        \text{PSSM score}(1, A) = \log_2 \left( \frac{0.6}{0.25} \right) = 1.263
        \]
        \[
        \text{PSSM score}(1, C) = \log_2 \left( \frac{0.2}{0.25} \right) = -0.322
        \]
        \[
        \text{PSSM score}(1, G) = \log_2 \left( \frac{0.1}{0.25} \right) = -1.322
        \]
        \[
        \text{PSSM score}(1, T) = \log_2 \left( \frac{0.1}{0.25} \right) = -1.322
        \]
 \end{frame}

\begin{frame}{Complete PSSM with Laplace's Rule (All Columns)}
    \textbf{Aligned Sequences:}
    \begin{itemize}
        \item Consider the following aligned DNA sequences:
        \[
        \begin{array}{cccccc}
        A &amp; A &amp; C &amp; T &amp; T &amp; A \\
        A &amp; A &amp; T &amp; T &amp; T &amp; C \\
        A &amp; T &amp; T &amp; T &amp; A &amp; A \\
        C &amp; A &amp; A &amp; A &amp; A &amp; A \\
        A &amp; T &amp; A &amp; A &amp; G &amp; A \\
        A &amp; T &amp; G &amp; A &amp; A &amp; T
        \end{array}
        \]
    \end{itemize}
\end{frame}

\begin{frame}{Step 1: Raw Counts and Adjusted Counts}
    \textbf{Raw Counts:}
    \[
    \begin{array}{c|cccccc}
    \text{NT} &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\
    \hline
    A &amp; 5 &amp; 3 &amp; 2 &amp; 3 &amp; 3 &amp; 4 \\
    C &amp; 1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 1 \\
    G &amp; 0 &amp; 0 &amp; 1 &amp; 0 &amp; 1 &amp; 0 \\
    T &amp; 0 &amp; 3 &amp; 2 &amp; 3 &amp; 2 &amp; 1 \\
    \end{array}
    \]

    \textbf{Adjusted Counts (with pseudocount of 1 added to all nucleotides):}
    \[
    \begin{array}{c|cccccc}
    \text{NT} &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\
    \hline
    A &amp; 6 &amp; 4 &amp; 3 &amp; 4 &amp; 4 &amp; 5 \\
    C &amp; 2 &amp; 1 &amp; 2 &amp; 1 &amp; 1 &amp; 2 \\
    G &amp; 1 &amp; 1 &amp; 2 &amp; 1 &amp; 2 &amp; 1 \\
    T &amp; 1 &amp; 4 &amp; 3 &amp; 4 &amp; 3 &amp; 2 \\
    \end{array}
    \]
\end{frame}

\begin{frame}{Step 2: Adjusted Probabilities}
    \textbf{Total Sequences + Pseudocount Adjustment:} \( N + 4 = 6 + 4 = 10 \)
    
    \textbf{Adjusted Probabilities for Each Nucleotide:}
    \[
    \begin{array}{c|cccccc}
    \text{NT} &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\
    \hline
    A &amp; \frac{6}{10} = 0.6 &amp; \frac{4}{10} = 0.4 &amp; \frac{3}{10} = 0.3 &amp; \frac{4}{10} = 0.4 &amp; \frac{4}{10} = 0.4 &amp; \frac{5}{10} = 0.5 \\
    C &amp; \frac{2}{10} = 0.2 &amp; \frac{1}{10} = 0.1 &amp; \frac{2}{10} = 0.2 &amp; \frac{1}{10} = 0.1 &amp; \frac{1}{10} = 0.1 &amp; \frac{2}{10} = 0.2 \\
    G &amp; \frac{1}{10} = 0.1 &amp; \frac{1}{10} = 0.1 &amp; \frac{2}{10} = 0.2 &amp; \frac{1}{10} = 0.1 &amp; \frac{2}{10} = 0.2 &amp; \frac{1}{10} = 0.1 \\
    T &amp; \frac{1}{10} = 0.1 &amp; \frac{4}{10} = 0.4 &amp; \frac{3}{10} = 0.3 &amp; \frac{4}{10} = 0.4 &amp; \frac{3}{10} = 0.3 &amp; \frac{2}{10} = 0.2 \\
    \end{array}
    \]
\end{frame}

\begin{frame}{Step 3: Log-Likelihood Ratios}
    \textbf{Log-Likelihood Ratios for Each Nucleotide (Using Background Probability \(P_{\text{bg}} = 0.25\)):} ~\\
    Logs are computed to base 2, i.e. $\log x \triangleq \log_2 x$
    {\small
    \[
    \begin{array}{c|cccccc}
    \text{NT} &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\
    \hline
    A &amp; \log \left(\frac{0.6}{0.25}\right)=1.263 &amp; 0.678 &amp; 0.263 &amp; 0.678 &amp; 0.678 &amp; 1.0 \\
    C &amp; \log \left(\frac{0.2}{0.25}\right)=-0.322 &amp; -1.322 &amp; -0.322 &amp; -1.322 &amp; -1.322 &amp; -0.322 \\
    G &amp; \log \left(\frac{0.1}{0.25}\right)=-1.322 &amp; -1.322 &amp; -0.322 &amp; -1.322 &amp; -0.322 &amp; -1.322 \\
    T &amp; \log \left(\frac{0.1}{0.25}\right)=-1.322 &amp; 0.678 &amp; 0.263 &amp; 0.678 &amp; 0.263 &amp; -0.322 \\
    \end{array}
    \]
    }
\end{frame}

\begin{frame}{Complete PSSM with Log-Likelihood Ratios}
    \textbf{Final PSSM (Log-Likelihood Scores for Each Position):}
    \[
    \begin{array}{c|cccccc}
    \text{NT} &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 \\
    \hline
    A &amp; 1.263 &amp; 0.678 &amp; 0.263 &amp; 0.678 &amp; 0.678 &amp; 1.0 \\
    C &amp; -0.322 &amp; -1.322 &amp; -0.322 &amp; -1.322 &amp; -1.322 &amp; -0.322 \\
    G &amp; -1.322 &amp; -1.322 &amp; -0.322 &amp; -1.322 &amp; -0.322 &amp; -1.322 \\
    T &amp; -1.322 &amp; 0.678 &amp; 0.263 &amp; 0.678 &amp; 0.263 &amp; -0.322 \\
    \end{array}
    \]
\end{frame}

\subsection{Example - Matlab PSSM Calculations}
% Slide 1 - PSSM Calculation Overview
\begin{frame}{PSSM Calculation and Visualization Summary}
    \textbf{Steps for Calculating PSSM in MATLAB:}
    \begin{itemize}
        \item Step 1: Define aligned sequences.
        \item Step 2: Count occurrences of each nucleotide.
        \item Step 3: Apply Laplace's rule (pseudocounts).
        \item Step 4: Calculate log-likelihood ratios.
        \item Step 5: Visualize the PSSM as a heatmap.
    \end{itemize}
\end{frame}

% Slide 2 - Step 1: Define Aligned Sequences
\begin{frame}[fragile]{Step 1: Define Aligned Sequences}
    \textbf{MATLAB Code:}
    \begin{lstlisting}
% Step 1: Define the aligned DNA sequences
alignedSequences = [
    'AACATT';
    'AATATA';
    'AGCATT';
    'ATCATT';
    'AATGTA';
    'AGCGTT'];
    \end{lstlisting}
\end{frame}

% Slide 3 - Step 2: Count Nucleotide Occurrences
\begin{frame}[fragile]{Step 2: Count Nucleotide Occurrences}
    \textbf{MATLAB Code:}
    \begin{lstlisting}
% Step 2: Count nucleotide occurrences at each position
[numSeqs, seqLength] = size(alignedSequences);
counts = zeros(4, seqLength);  % A, C, G, T

for i = 1:seqLength
  for j = 1:numSeqs
    nucleotide = alignedSequences(j, i);
    switch nucleotide
       case 'A', counts(1, i) = counts(1, i) + 1;
       case 'C', counts(2, i) = counts(2, i) + 1;
       case 'G', counts(3, i) = counts(3, i) + 1;
       case 'T', counts(4, i) = counts(4, i) + 1;
     end
  end
end
    \end{lstlisting}
\end{frame}

% Slide 4 - Step 3: Apply Laplace's Rule
\begin{frame}[fragile]{Step 3: Apply Laplace's Rule (Pseudocounts)}
    \textbf{MATLAB Code:}
    \begin{lstlisting}
% Step 3: Laplace's rule  to avoid zero probabilities
pseudocount = 1;
countsWithPseudo = counts + pseudocount;

% Calculate total counts per column after adding
%  pseudocounts
totalCounts = sum(countsWithPseudo);
    \end{lstlisting}
\end{frame}

% Slide 5 - Step 4: Calculate Log-Likelihood Ratios
\begin{frame}[fragile]{Step 4: Calculate Log-Likelihood Ratios}
    \textbf{MATLAB Code:}
    \begin{lstlisting}
% Step 4: Calculate PSSM (log-likelihood ratios)
backgroundFreq = 1 / 4;  % Equal background freq

PSSM = zeros(4, seqLength);  % To store the PSSM 
for i = 1:seqLength
 for j = 1:4
    % Frequency of nucleotide at current position
    frequency = countsWithPseudo(j, i) / totalCounts(i);
    % Log-likelihood ratio
    PSSM(j, i) = log2(frequency / backgroundFreq);
  end
end

disp('PSSM (Log-Likelihood Ratios):');
disp(PSSM);
    \end{lstlisting}
\end{frame}

% Slide 6 - Step 5: Visualize the PSSM
\begin{frame}[fragile]{Step 5: Visualize the PSSM as a Heatmap}
    \textbf{MATLAB Code:}
    \begin{lstlisting}
% Step 5: Visualization of PSSM as a heatmap
figure;
imagesc(PSSM);  % Display the PSSM matrix as an image
colorbar;       % Add color scale
xticks(1:seqLength);
yticks(1:4);
yticklabels({'A', 'C', 'G', 'T'});
xlabel('Position in Sequence');
ylabel('Nucleotide');
title('Position-Specific Scoring Matrix (PSSM)');
    \end{lstlisting}
\end{frame}

% Slide 7 - Summary of MATLAB PSSM Calculation
\begin{frame}{Summary of PSSM Calculation in MATLAB}
    \textbf{Steps Recap:}
    \begin{itemize}
        \item Define aligned DNA sequences.
        \item Count occurrences of each nucleotide.
        \item Apply Laplace's rule to avoid zero probabilities.
        \item Calculate log-likelihood ratios for each position.
        \item Visualize the PSSM using a heatmap.
    \end{itemize}
    
    \textbf{MATLAB Output:}
    \begin{itemize}
        \item The PSSM matrix provides insights into the likelihood of nucleotides at specific positions in the alignment.
        \item The heatmap offers a visual representation of the PSSM values.
    \end{itemize}
\end{frame}



% Slide 15 - Sliding Window
\begin{frame}{Sliding Window}
    \begin{itemize}
        \item A sliding window is applied to a sequence to locate patterns.
        \item The pattern is moved across the sequence, and scores are computed to find the best match.
    \end{itemize}
\end{frame}

\begin{frame}{Sliding Window Search with PSSM}
    \textbf{Concept of Sliding Window:}
    \begin{itemize}
        \item A sliding window search applies the PSSM over a sequence to find regions that match the pattern defined by the PSSM.
        \item The window moves across the sequence one position at a time, calculating a score at each step.
        \item The score is the sum of the log-likelihood ratios from the PSSM for the nucleotides in the window.
    \end{itemize}

    \textbf{Example DNA Sequence:}
    \begin{itemize}
        \item Consider the sequence:
        \[
        \text{SEQ} = \text{GATTACCGTT}
        \]
        \item The PSSM defines a pattern of length 6, so we slide a window of size 6 across the sequence.
    \end{itemize}
\end{frame}

\begin{frame}{Sliding Window Example}
    \textbf{Step 1: Apply PSSM to First Window (Positions 1-6):}~\\
    \textbf{Window 1} = \texttt{GATTAC}

    \begin{itemize}
        \item For each position in the window, use the corresponding PSSM score:
        
        \begin{dmath*}
        \text{Score} = \text{PSSM}(1,G) + \text{PSSM}(2,A) + \text{PSSM}(3,T) + \text{PSSM}(4,T) + \text{PSSM}(5,A) + \text{PSSM}(6,C)
        \end{dmath*}
        \item Using the final PSSM matrix from earlier:
        \[
        \text{Score} = -1.322 + 0.678 + 0.263 + 0.678 + 0.678 + -0.322 = 0.653
        \]
    \end{itemize}

    \textbf{Step 2: Slide the Window to Positions 2-7 and Repeat:}~\\ 
    \textbf{Window 2} = \texttt{ATTACC}
  
    \begin{itemize}
        \item The score for this window is calculated similarly by summing the corresponding PSSM values.
        \[
        \text{Score} = \text{PSSM}(1, A) + \text{PSSM}(2, T) + \dots + \text{PSSM}(6, C)
        \]
    \end{itemize}
\end{frame}

\begin{frame}{Sliding Window Results}
    \textbf{Sliding Window Summary:}
    \begin{itemize}
        \item Score computed for each position as the window slides 
        \item High scores indicate regions that closely match the pattern defined by the PSSM.
        \item The window position with the highest score is the most likely match for the pattern.
    \end{itemize}

    \textbf{Visualization:}
    \begin{itemize}
        \item Sliding the window over the sequence:
        \[
        \text{GATTACCGTT}
        \]
        \item Example window scores:
        \[
        \begin{array}{c|c}
        \text{Window} &amp; \text{Score} \\
        \hline
        GATTAC &amp; 0.653 \\
        ATTACC &amp; 0.359 \\
        TTACCG &amp; -0.423 \\
        TACCGT &amp; 0.512 \\
        ACCGTT &amp; -0.734 \\
        \end{array}
        \]
        \item The window \( GATTAC \) has the highest score, so it is the most likely match for the pattern.
    \end{itemize}
\end{frame}

% Slide 1 - Introduction to PSSM Search in MATLAB
\begin{frame}{Searching a Sequence for PSSM Match}
    \textbf{Goal:} Search a sequence for regions that match a Position-Specific Scoring Matrix (PSSM).
    
    \textbf{Key Steps:}
    \begin{itemize}
        \item Step 1: Define the PSSM and the search sequence.
        \item Step 2: Slide the PSSM along the sequence to compute the score at each position.
        \item Step 3: Identify the positions with the highest scores as potential matches.
    \end{itemize}
\end{frame}

% Slide 2 - Step 1: Define the PSSM and Sequence
\begin{frame}[fragile]{Step 1: Define the PSSM and Sequence}
    \textbf{MATLAB Code:}
    \begin{lstlisting}
% Step 1: Define the PSSM matrix (example: 4x6 matrix for A, C, G, T)
PSSM = [
    1.263, 0.678, 0.263, 0.678, 0.678, 1.0;
   -0.322, -1.322, -0.322, -1.322, -1.322, -0.322;
   -1.322, -1.322, -0.322, -1.322, -0.322, -1.322;
   -1.322,  0.678,  0.263,  0.678,  0.263, -0.322];

% Define the sequence to search for a match
sequence = 'GATTACCGTTGATTACAAGTAC';
sequenceLength = length(sequence);
PSSM_length = size(PSSM, 2);  % Length of PSSM matrix
    \end{lstlisting}
\end{frame}

% Slide 3 - Step 2: Sliding the PSSM Along the Sequence
\begin{frame}[fragile]{Step 2: Sliding the PSSM Along the Sequence}
    \textbf{MATLAB Code:}
    \begin{lstlisting}
% Step 2: Slide the PSSM along the sequence
nucleotides = 'ACGT';  % Nucleotide alphabet
% vector to store PSSM scores
scores = zeros(1, sequenceLength - PSSM_length + 1); 

% Loop through the sequence, sliding the PSSM
for i = 1:(sequenceLength - PSSM_length + 1)
    subsequence = sequence(i:i + PSSM_length - 1);
    score = 0;
    
    % Calculate the score for the current subsequence
    for j = 1:PSSM_length
        nucleotide = subsequence(j);
        pos = find(nucleotides == nucleotide);
        score = score + PSSM(pos, j);
    end
    scores(i) = score;  % Store the score for position
end
    \end{lstlisting}
\end{frame}

% Slide 4 - Step 3: Identify the Best Match
\begin{frame}[fragile]{Step 3: Identify the Best Match}
    \textbf{MATLAB Code:}
    \begin{lstlisting}
% Step 3: Find the position with the highest score
[bestScore, bestPosition] = max(scores);

% Display the best matching subsequence and score
fprintf('Best matching subsequence: %s\n', ...
 sequence(bestPosition:(bestPosition+PSSM_length-1)));
fprintf('Best score: %.3f\n', bestScore);

% Visualize the scores along the sequence
figure;
plot(scores);
xlabel('Position in Sequence');
ylabel('PSSM Score');
title('PSSM Match Scores Across the Sequence');
    \end{lstlisting}
\end{frame}

% Slide 5 - Summary of PSSM Search
\begin{frame}{Summary of PSSM Search}
    \textbf{Steps Recap:}
    \begin{itemize}
        \item Define the PSSM matrix and the sequence to be searched.
        \item Slide the PSSM along the sequence and calculate the score at each position.
        \item Identify the position with the highest score and visualize the scores along the sequence.
    \end{itemize}
    
    \textbf{Output:}
    \begin{itemize}
        \item The best matching subsequence is displayed with its corresponding PSSM score.
        \item A plot of PSSM scores across the sequence helps visualize the matching regions.
    \end{itemize}
\end{frame}

% Slide 16 - Hidden Markov Model (HMM)
\section{Hidden Markov Models}
%%%%%%%%%%%%%%%%%%%%%%


\begin{frame}{Hidden Markov Model (HMM) Overview}
    \textbf{Introduction to Hidden Markov Models (HMM):}
    \begin{itemize}
        \item An HMM is a statistical model where the system is assumed to follow a Markov process with hidden states.
        \item In bioinformatics, HMMs are widely used to model DNA and protein sequences, especially to describe motifs, domains, and sequence alignments.
    \end{itemize}

    \textbf{Components of HMM:}
    \begin{itemize}
        \item \textbf{States}: Hidden states that are not directly observable (e.g., match, insert, or delete states in sequence alignment).
        \item \textbf{Observations}: The visible symbols generated by the system (e.g., nucleotides or amino acids).
        \item \textbf{Transition Probabilities} \( A_{ij} \): The probability of moving from one state to another.
        \item \textbf{Emission Probabilities} \( B_i(k) \): The probability of emitting an observable symbol from a state.
    \end{itemize}
\end{frame}

% Slide 18 - Tools for Biological Patterns
\begin{frame}{Tools for Biological Patterns}
    \begin{itemize}
        \item Several tools, such as HMMER, are available for pattern discovery in biological sequences.
        \item These tools use multiple sequence alignments to generate HMMs.
    \end{itemize}
\end{frame}



\begin{frame}{Profile Hidden Markov Model (HMM) Overview}
    \textbf{What is a Profile HMM?}
    \begin{itemize}
        \item A Profile HMM is used to model the conserved regions and patterns in multiple sequence alignments (MSA).
        \item It consists of:
        \begin{itemize}
            \item \textbf{Match States (M)}: Represent conserved positions in the alignment.
            \item \textbf{Insert States (I)}: Represent insertions in the alignment.
            \item \textbf{Delete States (D)}: Represent deletions in the alignment.
        \end{itemize}
    \end{itemize}

    \textbf{Building Blocks of a Profile HMM:}
    \begin{itemize}
        \item **Transition probabilities** between match, insert, and delete states.
        \item **Emission probabilities** for nucleotides (or amino acids) in match and insert states.
    \end{itemize}
\end{frame}


\begin{frame}[fragile]{Hidden Markov Model - MSA with Gaps}
\begin{figure}[h]
\parbox[t]{0.8in}{
\begin{singlespace}
\begin{center}
\begin{tabular}{ccccccc} \hline
  {seq-1} &amp; G &amp; C &amp; C &amp; C &amp; A &amp; \\
  {seq-2} &amp; A &amp; G &amp; C &amp;   &amp;  &amp;  \\
  {seq-3} &amp; A &amp; A &amp; G &amp; C &amp;  &amp;  \\
  {seq-4} &amp; A &amp; G &amp; A &amp; A &amp;  &amp;  \\
  {seq-5} &amp; A &amp; A &amp; A &amp; C &amp;  &amp;  \\
  {seq-6} &amp; A &amp; G &amp; C &amp;   &amp;  &amp;  \\ \hline
          &amp;   &amp;   &amp;   &amp;   &amp;   &amp;
\end{tabular}
(a)
\end{center}
\end{singlespace}}
\hfill
\parbox[t]{2.3in}{
\begin{singlespace}
\begin{center}
\begin{tabular}{cccccccc} \hline
  {seq-1} &amp; $\phi$ &amp; $\phi$ &amp; G &amp; C &amp; C &amp; C &amp; A \\
  {seq-2} &amp; $\phi$ &amp; A &amp; G &amp; C &amp; $\phi$ &amp; $\phi$ &amp; $\phi$  \\
  {seq-3} &amp; A &amp; A &amp; G &amp; C &amp; $\phi$ &amp; $\phi$ &amp; $\phi$ \\
  {seq-4} &amp; $\phi$ &amp; A &amp; G &amp; A &amp; A &amp; $\phi$ &amp; $\phi$  \\
  {seq-5} &amp; $\phi$ &amp; A &amp; A &amp; A &amp; C &amp; $\phi$ &amp; $\phi$ \\
  {seq-6} &amp; $\phi$ &amp; A &amp; G &amp; C &amp; $\phi$ &amp; $\phi$ &amp; $\phi$\\
  \hline
  &amp; * &amp; $M_1$ &amp; $M_2$ &amp; $M_3$&amp; * &amp; * &amp; * \\ \hline
\end{tabular}
(b)
\end{center}
\end{singlespace}}
\caption{The set of sequences in (a) are aligned and shown in (b).}
\label{fig:align_example}
\hrulefill
\end{figure}
\end{frame}


\begin{frame}{Model and Transitions}
\begin{figure}[h]
\begin{center}
\parbox{3.5in}{
\includegraphics[width=3.5in]{Figures/HmmTopology.pdf}
\begin{center}(a)\end{center}}
\end{center}
\begin{center}
\parbox{3.0in}{
\begin{singlespace}
\small
\begin{tabular}{ccccccccc} \hline
  {seq-1} &amp; $M_0$ &amp; $D_1$ &amp; $M_2$ &amp; $M_3$ &amp; $I_3$ &amp; $I_3$ &amp; $I_3$ &amp;
$M_4$ \\
  {seq-2} &amp; $M_0$ &amp; $M_1$ &amp; $M_2$ &amp; $M_3$ &amp; $M_4$ &amp;       &amp;       &amp;
\\
  {seq-3} &amp; $M_0$ &amp; $I_0$ &amp; $M_1$ &amp; $M_2$ &amp; $M_3$ &amp; $M_4$ &amp;       &amp;
\\
  {seq-4} &amp; $M_0$ &amp; $M_1$ &amp; $M_2$ &amp; $M_3$ &amp; $I_3$ &amp; $M_4$ &amp;       &amp;
\\
  {seq-5} &amp; $M_0$ &amp; $M_1$ &amp; $M_2$ &amp; $M_3$ &amp; $I_3$ &amp; $M_4$ &amp;       &amp;
\\
  {seq-6} &amp; $M_0$ &amp; $M_1$ &amp; $M_2$ &amp; $M_3$ &amp; $M_4$ &amp;       &amp;       &amp;
\\
  \hline
\end{tabular}
\normalsize
\begin{center}(b)\end{center}
\end{singlespace}}
\end{center}
\caption{The consensus columns are used to define the match states
$M_1$, $M_2$ and $M_3$ for the {HMM}. After having defined the match
states, the corresponding insert and delete states are defined to
complete the profile-{HMM} topology.}
\label{fig:hmm_topology}
\hrulefill
\end{figure}
\end{frame}


\begin{frame}{Transition Probabilities}
\begin{figure}[h]
\parbox{1.0in}{
\begin{singlespace}
\tiny
\begin{tabular}{|l|cccc|} \hline
    &amp; \multicolumn{4}{c|}{State} \\ 
    &amp; 0 &amp; 1 &amp; 2 &amp; 3 \\ \hline
M$\rightarrow$M &amp; 4 &amp; 5 &amp; 6 &amp; 3 \\
M$\rightarrow$D &amp; 1 &amp; 0 &amp; 0 &amp; - \\
M$\rightarrow$I &amp; 1 &amp; 0 &amp; 0 &amp; 3 \\
\hline
I$\rightarrow$M &amp; 1 &amp; 0 &amp; 0 &amp; 2 \\
I$\rightarrow$D &amp; 0 &amp; 0 &amp; 0 &amp; - \\
I$\rightarrow$I &amp; 0 &amp; 0 &amp; 0 &amp; 2 \\
\hline
D$\rightarrow$M &amp; - &amp; 1 &amp; 0 &amp; 0 \\
D$\rightarrow$D &amp; - &amp; 0 &amp; 0 &amp; - \\
D$\rightarrow$I &amp; - &amp; 0 &amp; 0 &amp; 0 \\
\hline
\end{tabular}
\normalsize
\end{singlespace}}
\hfill
\parbox{3.0in}{
\includegraphics[width=3.0in]{Figures/HmmTransProbs.pdf}}
\caption{The state transitions inferred from the above topology are used to compute the frequency of transitions for the various states
in the model and state transition sequences in Fig.~\ref{fig:hmm_topology}. These frequency values are subsequently
utilized to compute the transition probabilities shown on the model above. Laplace rule is used to avoid zero probabilities.}
\label{HmmTransitionProbs}
\hrulefill
\end{figure}
\end{frame}


\begin{frame}{Emission Probabilities}
\begin{figure}[h]
\parbox{1.0in}{
\begin{singlespace}
\tiny
\begin{tabular}{|l|cccc|} \hline
    &amp; \multicolumn{4}{c|}{State} \\  
    &amp; 0 &amp; 1 &amp; 2 &amp; 3 \\ \hline 
      \multicolumn{5}{|c|}{{\small Match Emissions}} \\ \hline
{\bf A}   &amp; - &amp; 5 &amp; 1 &amp; 2 \\
{\bf C}   &amp; - &amp; 0 &amp; 0 &amp; 4 \\
{\bf G}   &amp; - &amp; 0 &amp; 5 &amp; 0 \\
{\bf T}   &amp; - &amp; 0 &amp; 0 &amp; 0 \\
\hline
     \multicolumn{5}{|c|}{{\small Insert Emissions}} \\ \hline
{\bf A}  &amp; 1 &amp; 0 &amp; 0 &amp; 1 \\
{\bf C}  &amp; 0 &amp; 0 &amp; 0 &amp; 2 \\
{\bf G}  &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\
{\bf T}  &amp; 0 &amp; 0 &amp; 0 &amp; 0 \\ 
\hline
\end{tabular}
\normalsize
\end{singlespace}}
\hfill
\parbox{3.0in}{
\includegraphics[width=3.0in]{Figures/HmmEmissionProbs.pdf}}
\caption{The state specific frequency of observation of a symbol is used for determining the probabilities of emissions. Again, Laplace rule is used to avoid zero probabilities.}
\label{HmmEmissionProbs}
\hrulefill
\end{figure}
\end{frame}

\begin{frame}{The Viterbi Algorithm: Overview}
    \textbf{What is the Viterbi Algorithm?}
    \begin{itemize}
        \item The Viterbi Algorithm is a dynamic programming algorithm used to find the most likely sequence of hidden states that explains an observed sequence.
        \item It works by calculating the most probable path through an HMM, maximizing the joint probability of the state sequence and the observed sequence.
    \end{itemize}

    \textbf{Applications:}
    \begin{itemize}
        \item Widely used in bioinformatics to determine the best alignment of sequences, gene prediction, protein structure modeling, and more.
        \item Example: Given a DNA sequence, we can use the Viterbi algorithm to identify the most probable path of hidden states (e.g., match, insert, or delete) in a Profile HMM.
    \end{itemize}
\end{frame}


\subsection{HMM in Matlab}
\begin{frame}[fragile]{HMM in Matlab - Build a MSA}

\begin{verbatim}
SeqMultiAligned = multialign (seqs, 'ScoringMatrix', s, 
                                    'GapOpen', g, 
                                    'ExtendedGap', e, 
                                    'TerminalGapAdjust', t
                              )
\end{verbatim}

All parameters, except for \emph{seqs}, are optional. The parameter \emph{seqs} is a vector of structures with the fields 'Sequence' for the residues and 'Header' for labels. The parameter \emph{seqs} may alos be a cell array of strings or a character array. 
\end{frame} 


\begin{frame}[fragile]{MSA}
\small
\begin{verbatim}
&gt;&gt; s1= {'AAAC'};
&gt;&gt; s2= {'AAAACT'};
&gt;&gt; s3= {'ACACTAC'};
&gt;&gt; seq = [s1; s2; s3]

seq =
    'AAAC'
    'AAAACT'
    'ACACTAC'

&gt;&gt; ma =  multialign(seq)

ans =
    AAA---C
    AAAAC-T
    ACACTAC
\end{verbatim}

The consensus sequence show six match states. 
\normalsize
\end{frame} 

\begin{frame}[fragile]{Functions for Building and Inducing HMM}
\begin{tabular}{|l|l|}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  hmmprofstruct &amp; Construct an HMM. \\ \hline
  hmmprofestimate &amp; Induce an HMM  from an alignment \\ \hline
  showhmmprof &amp; Display an HMM \\ \hline
  [s, a] = hmmprofalign &amp; Align a sequence to an HMM returning score and alignment\\ \hline
  hmmprofgenerate &amp; Generate new sequences from the HMM\\ \hline
  pfamhmmread &amp; Reads an HMM from a file \\ 
  \hline
\end{tabular}

\vspace{0.15in}
Hidden Markov Models will be constructed using function \emph{hmmprofstruct} and the probabilities will be computed with \emph{hmmprofestimate}.
\end{frame} 

\begin{frame}[fragile]{Induce HMM from MSA}
\small
\begin{verbatim}
&gt;&gt; hmm = hmmprofstruct (6, 'Alphabet', 'NT')
hmm =
        ModelLength: 6
           Alphabet: 'NT'
      MatchEmission: [6x4 double]
     InsertEmission: [6x4 double]
       NullEmission: [0.2500 0.2500 0.2500 0.2500]
             BeginX: [7x1 double]
             MatchX: [5x4 double]
            InsertX: [5x2 double]
            DeleteX: [5x2 double]
    FlankingInsertX: [2x2 double]
              LoopX: [2x2 double]
              NullX: [2x1 double]

&gt;&gt; maHmm = hmmprofestimate(hmm, ma)
&gt;&gt; showhmmprof(maHmm)
\end{verbatim}
\end{frame} 

\begin{frame}[fragile]{Finding HMM Patterns in a Sequence}
\small
\begin{verbatim}
&gt;&gt; seq = "CCCGGGCCACAATTTAAATCCCGGGGG";
&gt;&gt; [score, alignment] = hmmprofalign (maHmm, seq)

score =

    1.3516

alignment =

    'AAATCC'
\end{verbatim}
Command will show the scoring space:
\begin{verbatim}
&gt;&gt; [score, alignment] = 
      hmmprofalign (maHmm, seq, 'SHOWSCORE',true)
\end{verbatim}
\end{frame}

\subsection{PFAM}

\begin{frame}[fragile]{PFAM Database}
\small
\begin{itemize}
\item Pfam or Protein families is a database of known protein domains and patterns
\item Pfam is a  collection of multiple sequence alignments and hidden Markov models for many protein domains and families
\item A HMM downloaded from the PFAM database can be read into MATLAB using the function: \emph{pfamhmmread(fileName)}
\item Each Pfam family is given a unique accession number. Provides phylogentic information of the sequences used to create the model. 
\item For example, the Globin protein family has an accession number of \verb+PF00042+. The raw HMM model may be downloaded for each of the protein families. \textsc{Matlab} allows downloading and viewing the phylogenetic tree for the sequences:
\end{itemize}
\end{frame} 

\begin{frame}{PFAM: Protein Families Database Overview}
    \textbf{What is PFAM?}
    \begin{itemize}
        \item PFAM is a database of protein families, each represented by multiple sequence alignments and profile hidden Markov models (HMMs).
        \item It is used to analyze protein sequences to identify domains, classify proteins into families, and understand their evolutionary relationships.
    \end{itemize}

    \textbf{Key Components of PFAM:}
    \begin{itemize}
        \item \textbf{Families}: Collections of related proteins.
        \item \textbf{Domains}: Functional or structural units within proteins.
        \item \textbf{Repeats}: Short motifs that form stable structures when repeated.
        \item \textbf{HMMs}: Used to represent the consensus sequences of these families.
    \end{itemize}
\end{frame}


\begin{frame}[fragile]{Random Samples}
Generating a random nucleotide sequence of length 250:
\begin{verbatim}
&gt;&gt; randNT = randseq (250, 'Alphabet', 'NT');
\end{verbatim}
Generating a random protein sequence of length 250:
\begin{verbatim}
&gt;&gt; randAA = randseq (250, 'Alphabet', 'AA');
\end{verbatim}

Next we compute the score of aligning the Globins HMM with each of the nine globin sequences in the FASTA file \texttt{globins.fa}, and compare the score the alignment of a random amino acid sequence.
\end{frame}
%\begin{comment}

\begin{frame}[fragile]{Comparing Scores Intra Family Scores with Random Scores}
\begin{verbatim}
hmmGlobin = pfamhmmread('globinPfam.hmm');
seqLib = fastaread ('globins.fa');
for i = 1:length(seqLib)
  seq = seqLib(i).Sequence;
  score(i) = hmmprofalign (hmmGlobin, seq);
end
\end{verbatim}

These scores ranged from positive 50 to 125.

Compare this score with that of random amino acid sequence:
\begin{verbatim}
  randScore  = hmmprofalign (hmmGlobin, randAA);
\end{verbatim}

In comparison, the random sequence produced a score of -15 to -25. 
\end{frame} 



\begin{frame}{PFAM Data Access with MATLAB}
    \textbf{Downloading and Visualizing PFAM Data in MATLAB:}
    \begin{itemize}
        \item MATLAB provides functions to retrieve domain data from the PFAM database via HTTP requests and APIs.
        \item We can analyze domain architectures of proteins, visualize domains on protein sequences, and examine the alignment of sequences within a family.
    \end{itemize}
    
    \textbf{Steps:}
    \begin{enumerate}
        \item Download PFAM family data using an API.
        \item Parse and visualize the PFAM hidden Markov model (HMM) or domain structure on a protein sequence.
    \end{enumerate}
\end{frame}



\begin{frame}{Summary of Biological Patterns in Bioinformatics}
    \begin{itemize}
        \item Background Sequence Models - IID and Markov Models
        \item \textbf{Position-Specific Scoring Matrix (PSSM):}
        \begin{itemize}
            \item A tool used to represent the likelihood of observing a nucleotide or amino acid at each position in a biological sequence.
            \item Applied in sequence motif detection and scoring sequences against known motifs.
        \end{itemize}
        
        \item \textbf{Hidden Markov Models (HMMs):}
        \begin{itemize}
            \item Used to model biological sequences with hidden states (e.g., match, insert, and delete states).
            \item Applied in gene prediction, sequence alignment, and protein domain recognition.
        \end{itemize}
        
        \item \textbf{PFAM and Profile HMMs:}
        \begin{itemize}
            \item PFAM is a database of protein families represented by HMMs.
            \item Profile HMMs model conserved regions in multiple sequence alignments, enabling the identification of protein domains and families.
        \end{itemize}
        
    \textbf{Applications in Bioinformatics:}
    \begin{itemize}
        \item Analyzing conserved sequence motifs and functional domains in proteins.
        \item Predicting gene structures and identifying regulatory regions.
        \item Classifying sequences into protein families and domains.
    \end{itemize}
\end{itemize}
\end{frame}



\end{document}
</pre></body></html>