Bioinformatics and Algorithmic Genome Analysis: Study Guide

Course Overview & Primary Reference Materials

• Course Details:

  • Course Title: Bioinformatics
  • Course Code: CSE 469
  • Credit Hours: $3.0$
  • Total Course Hours: $36$

• Primary Reference Books:

  • Lehninger Principles of Biochemistry by Albert L. Lehninger, David L. Nelson, and Michael M. Cox.
  • Bioinformatics Algorithms: An Active Learning Approach Vol. 1 & 2 (2nd Edition) by Phillip Compeau and Pavel Pevzner.
  • An Introduction to Bioinformatics Algorithms by Neil C. Jones and Pavel A. Pevzner.

Introduction to Bioinformatics

• Definition: Bioinformatics is an academic field that seeks to create and advance algorithms, computational and statistical techniques, and theory to solve formal and practical problems arising from the management and analysis of biological data.

• Modes of Biological Experimentation:

  • In vivo: Experiments conducted within a living organism.
  • In vitro: Experiments conducted in an artificial environment (derived from Latin in glass).
  • In silico: Biological analysis conducted via computer simulation and software algorithms, derived by analogy from the silicon chips on which microprocessors are manufactured.

• Interdisciplinary Nature: Bioinformatics functions at the intersection of computer science, mathematics, statistics, chemistry, physics, biological science, and engineering to process, analyze, and interpret complex biological datasets.

Biological Organization and Cell Biology

• Fundamental Unit of Life:

  • A cell is the smallest structural unit of an organism that is capable of functioning independently.
  • Origin of life on Earth occurred approximately $3.5 \times 10^9\,\text{years}$ ($3.5\text{ billion years}$) ago.
  • Both prokaryotes and eukaryotes evolved from the same primitive ancestral cell $3.5 \times 10^9\,\text{years}$ ago.

• Chemical Composition of Cells (by weight):

  • Water: $70\%$
  • Small molecules (salts, lipids, amino acids, nucleotides): $7\%$
  • Macromolecules (proteins, polysaccharides, lipids): $23\%$

• Cellular Differentiation & Stem Cells:

  • Most somatic cells maintain fixed functional identities throughout their lifecycle (e.g., human skin cells remain skin cells).
  • Stem cells possess the unique capability to differentiate into any specialized cell type in the body.

• Comparative Structural Analysis:

  • Prokaryotes:

  • Single-celled organisms.

  • Cell size: Generally small ($1\text{--}10\,\mu\text{m}$).

  • Membrane-bounded organelles: Absent.

  • Genetic material: Single circular chromosome lacking nuclear membrane.

  • Primary examples: Bacteria.

  • Eukaryotes:

  • Unicellular or multicellular organisms.

  • Cell size: Generally large ($5\text{--}100\,\mu\text{m}$).

  • Membrane-bounded organelles: Present (e.g., nucleus, mitochondria, Golgi vesicles, peroxisomes, lysosomes, endoplasmic reticulum).

  • Genetic material: Linear chromosomes bound with histone proteins within a membrane-bound nucleus.

  • Primary examples: Plants, Animals.

• Chromosomal Architecture:

  • Eukaryotic genetic information is stored inside chromosomes made of chromatin (a complex of $\text{DNA}$ and protein) that condenses during cell division.
  • Chromosome count varies across eukaryotes, typically ranging between $10$ and $50$ chromosomes in somatic cells.
  • Human somatic body cells contain $46$ chromosomes, organized into $23$ nearly-identical pairs.

Nucleic Acid Chemistry and Molecular Structure

• Deoxyribonucleic Acid ($\text{DNA}$):

  • Known as the "Blueprint of Life", $\text{DNA}$ is the primary hereditary material in humans and nearly all living organisms.
  • Sub-cellular Location: Primarily located in the cell nucleus (nuclear $\text{DNA}$); a minor fraction is stored in mitochondria (mitochondrial $\text{DNA}$ or $\text{mtDNA}$).
  • Physical Dimensions and Packaging:
  • Organized as a multi-tiered coiling hierarchy ("coil of coils of coils…"), allowing $3 \times 10^9\,\text{base pairs}$ ($3\text{ billion base pairs}$) to fit inside a nucleus measuring approximately $6\,\mu\text{m}$ in diameter.
  • Stretched linearly, $\text{DNA}$ from a single human cell measures approximately $2\,\text{m}$ in length.
  • Stretched end-to-end, all $\text{DNA}$ in a human body equals twice the diameter of the Solar System.

• Structural Discovery & Subunits:

  • Double-helix structure elucidated by James Watson and Francis Crick.
  • Composed of repeating monomeric units termed nucleotides.

• Nucleotide Components:

  1. Nitrogenous base.
  2. Pentose sugar ($5\text{-carbon sugar}$: Deoxyribose in $\text{DNA}$, Ribose in $\text{RNA}$).
  3. Phosphate group.
  • Attachment sites: Phosphate group bonds to the $5'$ carbon of the sugar; nitrogenous base bonds to the $1'$ carbon of the sugar.

• Nitrogenous Base Classes:

  • Purines (Larger double-ring structures):
  • Adenine ($\text{A}$): Monomer derivative is Deoxyadenosine $5'\text{-phosphate}$ (dAMP).
  • Guanine ($\text{G}$): Monomer derivative is Deoxyguanosine $5'\text{-phosphate}$ (dGMP).
  • Pyrimidines (Smaller single-ring structures):
  • Cytosine ($\text{C}$): Monomer derivative is Deoxycytidine $5'\text{-phosphate}$ (dCMP).
  • Thymine ($\text{T}$ in $\text{DNA}$): Monomer derivative is Deoxythymidine $5'\text{-phosphate}$ (dTMP).
  • Uracil ($\text{U}$ in $\text{RNA}$).

• Chargaff's Rules of Base Pairing:

  • Purine Adenine ($\text{A}$) pairs exclusively with Pyrimidine Thymine ($\text{T}$) via $2$ Hydrogen bonds (bond lengths $2.8\,\text{\AA}$ and $3.0\,\text{\AA}$, overall width $11.1\,\text{\AA}$).
  • Purine Guanine ($\text{G}$) pairs exclusively with Pyrimidine Cytosine ($\text{C}$) via $3$ Hydrogen bonds (bond lengths $2.9\,\text{\AA}$ and $3.0\,\text{\AA}$, overall width $10.8\,\text{\AA}$).
  • Antiparallel Directionality: $\text{DNA}$ double strands run in opposite orientations ($5' \rightarrow 3'$ relative to $3' \rightarrow 5'$) and are standardly read in the $5' \rightarrow 3'$ direction.

• Ribonucleic Acid ($\text{RNA}$):

  • Single-stranded nucleic acid containing Ribose sugar and Uracil ($\text{U}$) in place of Thymine ($\text{T}$).
  • Major classes: messenger $\text{RNA}$ (mRNA), transfer $\text{RNA}$ (tRNA), ribosomal $\text{RNA}$ (rRNA).

Protein Structure and Function

• Protein Overview:

  • Large biomolecules (macromolecules) consisting of one or more linear chains of amino acid residues linked by peptide bonds.
  • Present in every cellular compartment; sequence dictated directly by $\text{DNA}$.

• Functional Classifications:

  • Antibody: Binds to foreign pathogens (e.g., viruses, bacteria) to protect the organism (Example: Immunoglobulin G / IgG).
  • Enzyme: Catalyzes biochemical reactions and processes genetic information (Example: Phenylalanine hydroxylase).
  • Messenger: Transmits chemical signals to coordinate biological processes across tissues and organs (Example: Growth hormone).
  • Structural Component: Provides scaffold support and enables physical movement (Example: Actin).
  • Transport / Storage: Binds and transports atoms and small molecules within cells and body fluids (Example: Ferritin).

• Amino Acid Chemistry:

  • Organic molecules featuring a central alpha-carbon ($\alpha\text{-carbon}$) covalently bonded to:
  1. An Amino group ($-\text{NH}_2$).
  2. A Carboxylic Acid group ($-\text{COOH}$).
  3. A Hydrogen atom ($-\text{H}$).
  4. A variable Side Chain ($-\text{R}$ group).
  • Polymerization: Linked via peptide bonds formed through a condensation reaction that releases a water molecule ($\text{H}_2\text{O}$) while connecting the carboxyl group of one amino acid to the amino group of the next. The resulting linear sequence represents the protein's primary structure.

• The 20 Standard Amino Acids:

  1. Alanine (Ala, A)
  2. Arginine (Arg, R)
  3. Asparagine (Asn, N)
  4. Aspartic acid (Asp, D)
  5. Cysteine (Cys, C)
  6. Glutamine (Gln, Q)
  7. Glutamic acid (Glu, E)
  8. Glycine (Gly, G)
  9. Histidine (His, H)
  10. Isoleucine (Ile, I)
  11. Leucine (Leu, L)
  12. Lysine (Lys, K)
  13. Methionine (Met, M)
  14. Phenylalanine (Phe, F)
  15. Proline (Pro, P)
  16. Serine (Ser, S)
  17. Threonine (Thr, T)
  18. Tryptophan (Trp, W)
  19. Tyrosine (Tyr, Y)
  20. Valine (Val, V)

The Central Dogma of Molecular Biology

• Conceptual Framework:

  • Formulated by Francis Crick, describing the unidirectional flow of biological information: $\text{DNA} \rightarrow \text{RNA} \rightarrow \text{Protein}$.
  • Though termed a "dogma" at a time when limited empirical evidence existed, it has since been validated as a foundational principle.

• Core Processes:

  1. Replication: Copying parental $\text{DNA}$ to yield daughter $\text{DNA}$ molecules with identical nucleotide sequences.
  2. Transcription: Copying specific genetic sequences encoded in $\text{DNA}$ into an $\text{RNA}$ transcript.
  3. Translation: Decoding the genetic message carried by messenger $\text{RNA}$ on ribosomes to synthesize a polypeptide chain with a specific amino acid sequence.

DNA Replication Machinery and Dynamics

• Mechanism of Synthesis:
  1. Unwinding: Helicase breaks hydrogen bonds between complementary base pairs ($\text{A-T}$, $\text{C-G}$), opening the double helix into a Y-shaped replication fork.
  2. Template Orientation:
  • Leading strand template: Oriented $3' \rightarrow 5'$ toward the replication fork.
  • Lagging strand template: Oriented $5' \rightarrow 3'$ away from the replication fork.
  1. Primer Synthesis: Primase synthesizes short $\text{RNA}$ primers to provide free $3'\text{-OH}$ starting points.
  2. Polymerization:
  • $\text{DNA}$ polymerase reads templates $3' \rightarrow 5'$ and synthesizes new strands continuously or discontinuously in the $5' \rightarrow 3'$ direction.
  • Leading strand: Continuous elongation.
  • Lagging strand: Discontinuous elongation, producing short segments called Okazaki fragments.
  • Okazaki fragment length: Bacterial cells = $\approx 1,000\text{--}2,000\,\text{nucleotides}$; Eukaryotic cells = $150\text{--}200\,\text{nucleotides}$.
  1. Primer Excision & Ligation: Exonuclease removes $\text{RNA}$ primers, $\text{DNA}$ polymerase fills gaps with $\text{DNA}$ nucleotides, and $\text{DNA}$ ligase covalently seals the nicked sugar-phosphate backbone.
  2. Proofreading: Polymerase proofreads newly synthesized strands to ensure high-fidelity base pairing.
  3. Semi-Conservative Inheritance: Each daughter $\text{DNA}$ duplex contains one conserved original parent strand and one newly synthesized daughter strand.

Transcription and Post-Transcriptional Processing

• Stages of Transcription:
  1. Initiation: RNA polymerase binds to a promoter region on $\text{DNA}$ upstream ($5'$) of the start site. Promoters establish transcription direction and identify the template sense strand.
  • Eukaryotic TATA box: Conserved promoter element located $25\text{--}35\,\text{base pairs}$ upstream of the initiation site.
  1. Elongation: RNA polymerase unwinds the $\text{DNA}$ double helix, reads the template strand in the $3' \rightarrow 5'$ direction, and appends ribonucleotides to the $3'$ end of the growing pre-mRNA transcript.
  2. Termination: RNA polymerase reaches a termination signal on the $\text{DNA}$ template, causing dissociation of both enzyme and newly synthesized mRNA.

• Eukaryotic mRNA Processing:
  • Poly-A Tail Addition: Cleavage at the $3'$ end frees a $3'\text{-OH}$ group, where poly-A polymerase adds a tract of $100\text{--}250$ adenine residues (polyadenylation). Increases stability, prevents degradation, and facilitates nuclear export.
  • RNA Splicing: Non-coding intervening sequences (introns) are spliced out from pre-mRNA; remaining coding sequences (exons) are ligated together to produce mature mRNA.

Translation Mechanism and the Genetic Code

• Codon Architecture:
  • Genetic code is organized into triplets of mRNA bases called codons.
  • Written $5' \rightarrow 3'$; degeneracy allows multiple codons to specify the same amino acid.
  • Start codon: $\text{AUG}$ (codes for Methionine / $\text{Met}$).
  • Termination (Stop) codons: $\text{UAA}$, $\text{UAG}$, $\text{UGA}$.

• Translational Stages & Ribosomal Sites:
  • Ribosome Contains 3 Binding Sites:
  • $\text{A}$ site (Aminoacyl / Amino acid site): Accepts incoming charged tRNA.
  • $\text{P}$ site (Peptidyl / Polypeptide site): Holds tRNA attached to the growing peptide chain.
  • $\text{E}$ site (Exit site): Releases uncharged tRNA.
  • Initiation:
  • Small subunit binds mRNA at ribosome binding site.
  • Initiator tRNA carrying Methionine ($\text{Met}$ in eukaryotes) or Formylmethionine ($\text{fMet}$ in prokaryotes) pairs with start codon $\text{AUG}$ at the P site.
  • In prokaryotes, initiator tRNA binds after small subunit binds mRNA; in eukaryotes, initiator tRNA forms a complex with small subunit prior to mRNA binding.
  • Large ribosomal subunit joins to complete the initiation complex.
  • Elongation:
  • Elongation factors (e.g., $\text{EF-Tu}$, $\text{GTP}$, $\text{EF-Ts}$, $\text{EF-G}$) mediate entry of cognate tRNA into the open A site.
  • Peptide bond forms, transferring the growing peptide chain to the amino acid on the A-site tRNA.
  • Ribosome translocates one codon downstream ($5' \rightarrow 3'$), shifting A-site tRNA to P site, and P-site tRNA to E site.
  • Termination:
  • Release factors recognize stop codons ($\text{UAA}$, $\text{UAG}$, $\text{UGA}$) in the A site, triggering hydrolysis and release of the completed polypeptide and dissociation of ribosomal subunits.

Algorithmic Bioinformatics: Locating the Origin of Replication

• The Origin of Replication ($oriC$):

  • DNA replication initiates at specific genomic regions termed replication origins ($oriC$).
  • Experimental approach: Cutting $\text{DNA}$ fragments in vitro to test replication capability is a biological procedure, not an algorithmic solution.

• Hidden Message Hypothesis:

  • Initiation is mediated by $\text{DnaA}$ protein binding to short $\text{DNA}$ segments ($\approx 9\,\text{nucleotides}$ long) called DnaA boxes within $oriC$.
  • Multiple DnaA boxes clustered together act as hidden genomic signals instructing $\text{DnaA}$ to initiate unwinding.

• The Frequent Words Problem:

  • Problem Formulation:
  • Input: A string $Text$ and an integer $k$.
  • Output: All most frequent $k$-mers in $Text$.
  • Definition: A $k$-mer $Pattern$ is a most frequent $k$-mer in $Text$ if no other $k$-mer appears more frequently.
  • Example: In ACAAATTTGCATAATTTCGGGAAATTTCCT, the $5$-mer AATTT appears $3$ times.
  • Application to Vibrio cholerae $oriC$ ($\approx 500\,\text{bp}$):
  • Frequent $9$-mers appearing $3$ times: ATGATCAAG, CTTGATCAT, TCTTGGATCA, CTCTTGATC.
  • Incorporating Reverse Complements: $\text{DnaA}$ binds double-stranded $\text{DNA}$ without strand specificity. ATGATCAAG and CTTGATCAT are reverse complements of each other ($\text{ATGATCAAG} \parallel \text{CTTGATCAT}$). Counting both strands reveals a combined frequency of $6$, which is statistically unexpected within a short $500\,\text{bp}$ window.

• Species-Specific Variations in DnaA Boxes:

  • Thermotoga petrophila $oriC$ contains no occurrences of ATGATCAAG or CTTGATCAT.
  • Frequent $9$-mers in Thermotoga petrophila: AACCTACCA, ACCTACCAC, GGTAGGTTT, TGGTAGGTT, AAACCTACC, CCTACCACC.
  • Analysis via Ori-Finder software confirms CCTACCACC and its reverse complement GGATGGTGG as $oriC$ DnaA boxes.

Genome-Wide Discovery & The Clump Finding Problem

• The Genomic Search Challenge:

  • Predicting DnaA boxes works when $oriC$ is known, but locating $oriC$ in an unannotated full genome ($\approx 4.6 \times 10^6\,\text{bp}$) requires genome-wide search strategies.

• The Clump Finding Problem:

  • Intuitive Definition: A $k$-mer forms a clump if it appears multiple times within a short genomic interval.
  • Formal Definition: A $k$-mer forms an $(L, t)$-clump in $Genome$ if there exists an interval of length $L$ in which the $k$-mer appears at least $t$ times.
  • Problem Formulation:
  • Input: String $Genome$, integers $k$ (pattern length), $L$ (window length), and $t$ (frequency threshold).
  • Output: All $k$-mers forming $(L, t)$-clumps in $Genome$.
  • Limitations: In the E. coli genome, there exist $1904$ different $9$-mers forming $(500, 3)$-clumps, creating excessive noise to isolate $oriC$ purely by standard clumping.

Replication Asymmetry and Skew Diagrams

• Biological Asymmetry:

  • Bacterial replication proceeds bidirectionally from $oriC$ to terminus ($terC$).
  • Polymerase unidirectionality ($3' \rightarrow 5'$ reading) forces asymmetric strand synthesis:
  • Leading strand / Reverse half-strand: Remains double-stranded most of the time.
  • Lagging strand / Forward half-strand: Spends significant time single-stranded, waiting for replication fork opening between Okazaki fragment synthesis cycles.

• Cytosine Deamination Dynamics:

  • Single-stranded $\text{DNA}$ exhibits a $100\text{-fold}$ increase in Cytosine ($\text{C}$) deamination, rapidly mutating $\text{C}$ into Thymine ($\text{T}$).
  • Forward half-strand (single-stranded lifecycle): Significant shortage of $\text{C}$, normal levels of $\text{G}$.
  • Reverse half-strand (double-stranded lifecycle): Shortage of $\text{G}$, normal levels of $\text{C}$.
  • Empirical Data in E. coli:
  • Reverse half-strand: $\#C = 219,518$, $\#G = 201,634 \implies \#G - \#C = -17,884$
  • Forward half-strand: $\#C = 207,901$, $\#G = 211,607 \implies \#G - \#C = +3,706$
  • Total Net Difference: $\Delta\#C = +11,617$, $\Delta\#G = -9,973$

• Skew Diagram Construction:

  • Definition: $\text{Skew}(k) = \#G - \#C$ for the first $k$ nucleotides of $Genome$.
  • Dynamics along chromosome walk:
  • Walking along reverse half-strand: $\#G - \#C$ decreases monotonically ($\text{C}$ high, $\text{G}$ low).
  • Walking along forward half-strand: $\#G - \#C$ increases monotonically ($\text{C}$ low, $\text{G}$ high).
  • The global minimum of the Skew Diagram pinpointing the shift from decreasing to increasing skew marks the location of $oriC$.

• Frequent Words with Mismatches:
  • Evaluating the minimum region of $E. coli$ skew diagram reveals no exact canonical $9$-mers appearing $\ge 3$ times.
  • Biological reality: DnaA box binding tolerates nucleotide mutations.
  • Example in Vibrio cholerae: ATGATCAAC and CATGATCAT differ by $1$ mismatch from canonical ATGATCAAG/CTTGATCAT.
  • Frequent Words with Mismatches Problem Formulation:
  • Input: String $Text$, integers $k$ and $d$ (maximum mismatches).
  • Output: All most frequent $k$-mers with up to $d$ mismatches in $Text$.
  • Result in E. coli: Searching for frequent $9$-mers with $1$ mismatch and reverse complements identifies actual functional DnaA boxes: TGTGGATAA, TTATACACA, TTTGGATAAC, TTATCCACA.

Open Computational Problems in Genome Replication

• Bacterial Exceptions:

  • Some bacteria possess fewer DnaA boxes.
  • Replication terminus ($terC$) is not always situated directly opposite $oriC$.
  • Skew diagrams in certain species (e.g., Thermotoga, Wigglesworthia glossinidia) exhibit noisy or complex profiles.
  • Xia (2012) proposed that certain bacterial genomes contain multiple replication origins.

• Unresolved Frontiers (Open Problems):

  • Archaea: Archaea possess multiple replication origins (e.g., $3$ origins in Sulfolobus solfataricus), but no algorithm currently exists to predict them reliably.
  • Yeast & Eukaryotes: Yeast (Saccharomyces cerevisiae) genomes contain hundreds of replication origins; human genomes contain thousands. Developing reliable predictive software for eukaryotic multi-origin replication remains an active open research challenge.