Bioinformatics for Biologists: Comprehensive Study Notes

BIOINFORMATICS FOR BIOLOGISTS

Introduction to Bioinformatics and Computational Thinking

• Pedagogical Shift: The education of biologists is evolving to address complex data sets in life science research. The focus has moved from just using tools as "black boxes" to developing computational thinking from first principles.

• Role of Bioinformatics: Bioinformatics and computational biology are used interchangeably. They are as essential to 21st-century biology as molecular biology was to the 20th century. Research would slow significantly without tools like BLAST.

• Components of Bioinformatics: Consists of two main flavors: Databases (storing protein sequences, structures, annotations, and drug data) and Algorithms (procedures developed to analyze this data).

• The Recreational Mathematics Approach: Many core concepts (e.g., Eulerian cycles for genome assembly) can be introduced intuitively through recreational mathematics rather than complex mathematical formalism.

Computational Complexity and Algorithms

• Algorithm Definition: A "recipe" or step-by-step procedure for a computational task (e.g., long addition).

• Efficiency Measurement: Algorithms are evaluated based on the number of operations performed relative to the input size $n$.

• O Notation (Big Oh): Used to describe the rate of growth. An algorithm taking $15n^2 + 20n + 7$ operations is simplified to $O(n^2)$.

• Complexity Classes:

  • Polynomial: $O(n^c)$ for some constant $c$. Generally considered tractable.

  • Exponential: $O(2^n)$. Becomes computationally impossible very quickly as $n$ increases (e.g., increasing $n$ from 30 to 40 results in a 1024-fold increase in runtime).

• NP-Completeness: A set of thousands of problems for which no polynomial algorithm is known. If one is found for any single problem, all have polynomial solutions. Showing a problem is NP-complete indicates it is likely intractable for exact solutions on large inputs.

• Strategies for Hard (NP-Hard) Problems:

  • Approximation Algorithms: Polynomial algorithms that provide solutions provably near-optimal.

  • Probabilistic Algorithms: Run in polynomial time on average but may have exponential worst-case scenarios.

  • Heuristics: Fast algorithms that work well in practice but lack theoretical guarantees of optimality.

  • Exhaustive Algorithms: Try all possible solutions; practical only for small inputs.

Part I: Genomes and Genetic Analysis

Identifying the Genetic Basis of Disease

• Genotype and Phenotype: The genotype (genetic code) influences physico-chemical traits (phenotype).

• Single Nucleotide Polymorphisms (SNPs): Single nucleotide variations occurring at specific loci. If a variant affects a gene, it is called an allele.

• Mendelian Mutation: A simple case where carrying a specific mutation correlates perfectly with a phenotype.

• Coalescent Theory: The ancestral history of chromosomes represented as a tree. The Most Recent Common Ancestor (MRCA) is the point where the ancestry of a current population reduces to a single chromosome.

• Linkage and Recombination:

  • Principle of Linkage: Mutations on the same evolutionary lineage are correlated.

  • Recombination: Crossing over during meiosis destroys correlation (Linkage Equilibrium) as genomic distance between loci increases.

Statistical Tests for Association

• Linkage Disequilibrium (LD): The correlation between proximal loci. Measured by the $D$ statistic:

  • $D = P<em>{xy} - P</em>xP_y$

• Scaled Statistic ($D'$): Normalized between 0 and 1.

• Correlation Coefficient (\rho): Used to compute p-values via the $\chi^2$ test of independence:

  • $\chi^2 = \rho^2 n$

• Challenges: Epistasis (interactions between multiple loci), population substructure (confounding due to ethnic origins), and rare variants (low frequency but cumulative effect).

Pattern Identification in Haplotype Blocks

• Haplotype Blocks: High-LD regions partitioned by recombination hotspots.

• Tag SNPs: A small subset of SNPs sufficient to distinguish all patterns in a block, reducing genotyping costs.

• Computational Reductions: The Tag SNP selection problem can be reduced to:

  1. The Set-Covering Problem: Finding a minimum subcollection of sets to cover all elements. Solved via a greedy algorithm with a performance ratio of $\ln |U| + 1$.

  2. Integer Programming: Minimizing a linear objective function subject to linear constraints where variables must be integers (0 or 1). This is tackled using LP-relaxation and randomized rounding.

Genome Reconstruction (DNA Sequencing)

• The Overlap Puzzle: Genomes cannot be read nucleotide by nucleotide; instead, they are broken into short reads (approx. 100 nt) and reassembled.

• Mathematical Models:

  • Hamiltonian Cycle Problem (HCP): Assigning reads to nodes and finding a path that visits every node once. This is NP-complete and intractable for large genomes.

  • Eulerian Cycle Problem (ECP): Assigning reads to edges and $(l-1)$-mers to nodes. Finding a path traversing every edge once. This is solvable in polynomial time per Euler's Theorem.

• Euler's Theorem: A directed graph has an Eulerian cycle if and only if for every vertex, the indegree equals the outdegree.

• De Bruijn Graphs: Used in modern assembly. A graph $B(n, l)$ whose vertices are all words of length $l-1$, with edges representing $l$-mers.

Dynamic Programming (Alignment and Gene Recognition)

• Core Concept: Solving a complex problem by decomposing it into an ordered set of smaller subproblems (subpaths). Suboptimal subpaths are discarded early.

• Alignment: Finding the best correspondence between two sequences (DNA or Protein) by rewarding matches ($r$) and penalizing mismatches ($p$) and gaps ($q$).

  • Global Alignment: Uses a 2D lattice graph to find the highest-scoring path in $O(MN)$ time.

  • Local Alignment: Identifies the highest similarity region (e.g., Smith-Waterman).

• Gene Recognition: Identifying exons and introns. Modeled using an Exon-Intron Graph or a more efficient Segment Graph ($O(L)$ complexity).

Part II: Gene Transcription and Regulation

Replication and Transcription Effects

• Chargaff’s Parity Rules: A single DNA strand usually contains equal numbers of A/T and G/C, though skew occurs during specific processes.

• Cumulative Skew Diagrams: Used to identify the origin ($ori$) and terminus ($ter$) of replication. In bacteria, the leading strand accumulates G excess due to spontaneous deamination of C to T in single-stranded states.

Modeling Regulatory Motifs

• Transcription Factor Binding Sites (TFBS): Short (5–15 bp) DNA sequences where TFs bind.

• Representations:

  1. Consensus Sequence: Uses the most frequent nucleotide at each position.

  2. Position Weight Matrix (PWM): A probability matrix that assumes position independence.

  3. Maximum Dependence Decomposition (MDD): Uses a tree structure to model dependencies between positions via $\chi^2$ statistics.

• Information Content ($I_j$): Measured in bits ($0$ to $2$). Formula:

  • $I<em>j = 2 + \sum</em>{x \in {A,C,G,T}} f<em>{x,j} \log</em>2(f_{x,j})$

Part III: Evolution and Phylogeny

Genome Rearrangements

• Types: Reversal (inversion), Translocation, Fission, and Fusion.

• Synteny Blocks: Conserved genomic segments shared between species.

• Distance Metrics: Reversal distance minimizes the operations to transform one genome into another. For signed permutations (gene orientation known), this is solvable in linear time ($O(n)$).

• Double-Cut-and-Join (DCJ): A unified model for all rearrangement types, transforming genomes by rejoining DNA ends.

Phylogenetic Trees and the "Forest of Life"

• Vertical vs. Horizontal Transfer: Horizontal Gene Transfer (HGT) complicates the concept of a single Tree of Life (TOL).

• Statistical Central Trend: Analysis of thousands of gene trees (The Forest of Life) suggests that while histories differ, a central trend exists among Nearly Universal Trees (NUTs), primarily involved in translation and transcription.

• Maximum Parsimony: Finding a tree that minimizes the total number of character substitutions. This problem is NP-hard.

• Heuristics: Strategies like Nearest Neighbor Interchange (NNI) and Genetic Algorithms are used to navigate the vast "treespace."

Part IV: Regulatory Networks

• Interaction Networks: Model biological systems as nodes (proteins/genes) and edges (interactions).

• Topological Analysis:

  • Graphlets: Small induced subgraphs used to describe local network structure.

  • Graphlet Degree Vector (GDV): Generalizes node degree to characterize a node’s structural surroundings, aiding in predicting protein function and disease involvement.

• Network Alignment: Finding conserved regions across different species' networks (e.g., the GRAAL algorithm for topological alignment).