Bioinformatics Algorithms

Algorithms and mathematical ideas behind biological data analysis.

Low-dimensional omics representations and clustering

• Principal component analysis for omics data: variance-maximizing orthogonal components for QC, exploration, and covariate discovery
• Non-negative matrix factorization: additive nonnegative feature programs, sample exposures, rank selection, and stability
• k-means and k-medoids clustering: flat prototype-based partitions, robust medoids, choice of \(k\), and stability checks
• Hierarchical clustering: linkage-based nested partitions, dendrogram interpretation, and branch validation
• k-nearest-neighbor graphs: sparse local neighborhoods, graph construction choices, and downstream use in omics workflows
• t-SNE dimensionality reduction: probability-preserving local visualization, parameter sensitivity, and responsible interpretation
• UMAP dimensionality reduction: weighted neighbor-graph embeddings, parameter choices, and cautious interpretation of omics layouts
• Diffusion maps: random-walk geometry, diffusion components, and trajectory-aware exploration of continuous states
• Louvain community detection: greedy multilevel modularity optimization, graph communities, resolution limits, and stability diagnostics
• Leiden community detection: refined multilevel graph clustering, well-connected communities, resolution choice, and omics validation

Multiple comparisons and functional interpretation

• Multiple-testing correction: family-wise and false-discovery-rate control, ordered p-value procedures, and responsible omics interpretation
• Gene-set enrichment algorithms: over-representation and ranked-list tests, enrichment null models, leading-edge genes, and pathway-level inference

Database sequence search

• BLAST seed-and-extend search: word seeds, candidate extension, HSPs, and E-value interpretation
• FASTA sequence-search algorithm: diagonal word clustering and staged local-alignment refinement

k-mer representations and sketches

• k-mers and sequence composition: sequence words, counting, spectra, and the specificity–robustness trade-off
• Minimizers and sequence sketching: sparse local seeds for scalable sequence indexing, mapping, and assembly

Genome assembly graphs

• de Bruijn graphs for genome assembly: k-mer overlap graphs, unitigs, graph simplification, and repeat ambiguity
• Overlap–layout–consensus assembly: explicit read overlaps, graph layout, consensus polishing, and long-read assembly

Compressed sequence indexes

• Burrows–Wheeler transform: reversible sequence reordering, LF mapping, and context clustering
• FM-index for sequence search: backward search, rank queries, and compact exact reference lookup
• Suffix trees and suffix arrays: lexicographic full-text indexes for exact matches, repeats, and shared substrings
• Hash-based sequence indexing: k-mer lookup tables for seed retrieval and candidate generation

Read mapping and placement confidence

• Read mapping and seed chaining: sparse anchors, collinear chains, and local alignment of candidate loci
• Mapping quality estimation: Phred-scaled placement confidence, competitor alignments, and SAM/BAM interpretation

Hidden Markov models for sequences

• Pairwise hidden Markov models: probabilistic match/gap paths, Viterbi decoding, likelihoods, and alignment uncertainty
• Profile HMMs for protein families: position-specific family models for domain detection, alignment, and remote-homology search
• Viterbi and Forward–Backward algorithms: best hidden-state paths, model likelihoods, and posterior state confidence
• Expectation–maximization: iterative parameter learning from soft latent-state assignments, including Baum–Welch HMM training

Bayesian posterior inference

• Bayesian inference in bioinformatics: priors, likelihoods, posterior uncertainty, predictive checks, and biological model assumptions
• Markov chain Monte Carlo: posterior sampling, Metropolis–Hastings, phylogenetic tree sampling, and convergence diagnostics

Variant and haplotype inference

• Variant-calling likelihood models: read and haplotype likelihoods, genotype uncertainty, VCF confidence fields, and calibration
• Haplotype assembly and phasing: physical read links, graph partitioning, statistical phase, phase blocks, and switch errors

Copy number and structural variation

• Copy-number segmentation algorithms: change-points in noisy genomic signal, circular binary segmentation, and copy-number interpretation
• Structural-variant discovery algorithms: discordant pairs, split reads, depth, assembly, and breakpoint confidence

Phylogenetic distance and tree reconstruction

• Phylogenetic distance models: correction for multiple substitutions, model assumptions, saturation, and distance-matrix construction
• Neighbor-joining trees: distance-corrected agglomerative tree building, branch lengths, rooting, and bootstrap stability
• Maximum-likelihood phylogenetics: site-pattern likelihoods, pruning, tree-space search, evolutionary models, and branch support
• Bayesian phylogenetic inference: posterior tree distributions, priors, MCMC diagnostics, calibrations, and credible uncertainty

Graphs and optimization

• Dynamic programming in bioinformatics: recursive states, recurrences, traceback, complexity, and exact biological inference
• Integer linear programming in bioinformatics: constrained discrete choices, branch-and-cut, solver certificates, and formulation validation
• Minimum spanning trees in bioinformatics: sparse least-cost graph connection, greedy correctness, and cautious biological interpretation
• Shortest-path algorithms in biological graphs: weighted routes, Dijkstra assumptions, dynamic-programming connections, and network caveats
• Network-flow algorithms in bioinformatics: capacitated routing, residual graphs, min-cuts, and biological flow-model diagnostics
• Bipartite matching algorithms in bioinformatics: exclusive assignments, augmenting paths, weighted matching, and pairing uncertainty

Sequence and probabilistic models

Planned: further probabilistic sequence models and approximate-inference methods.

Pairwise sequence alignment

• Global sequence alignment: Needleman–Wunsch: optimal end-to-end alignment, scoring, traceback, affine gaps, and interpretation
• Local sequence alignment: Smith–Waterman: optimal subsequence alignment, local restart, statistical meaning, and practical diagnostics