computational-biology

Layer 3 — Biology24 concepts in this subtree

Computational biology — NSF BIO / DBI biological-informatics grain; computational methods applied to biological data (sequences, structures, networks, cellular state). Foundations: (1) Dynamic-programming sequence alignment:…

Needleman-Wunsch DP: dp[i][j] = max(dp[i−1,j−1]+s, dp[i−1,j]+g, dp[i,j−1]+g)
Levenshtein edit distance: min{ins, del, sub} ops; metric on Σ*
Hamming distance: d_H(x,y) = #{i: x_i ≠ y_i}; upper-bounds Levenshtein
NW canonical anchors: NW(AG,AG)=2, NW(AG,AC)=0, NW(ATGC,ATGC)=4
Levenshtein metric on canonical anchors: d(kitten,sitting) = 3, d(x,x)=0, symmetric
Hamming bound: d_L(AACT,AGCT) = d_H(AACT,AGCT) = 1; d_L ≤ d_H for |x|=|y|
BLAST Karlin-Altschul: E = K·m·n·exp(−λ·S); local-alignment-score EVT (Gumbel) framework
Jukes-Cantor JC69: dP/dt = Q·P; p(t) = 3/4·(1−e^{−4αt}); first-order Markov substitution model
Nussinov 1978 RNA folding: M(i,j) = max{M(i+1,j), M(i,j−1), M(i+1,j−1)+δ_{ij}, max_k M(i,k)+M(k+1,j)}
BLAST: E=K·m·n·exp(−λS); doubling n doubles E; S'=(λS−lnK)/ln2; anchor K=0.1,m=1000,n=10⁶,λ=1,S=20
JC69: p(t)=3/4·(1−exp(−4αt)); d(p)=−3/4·ln(1−4p/3); p_∞=3/4; dp/dt|₀=3α; d(p=3/8)=(3/4)ln2
Nussinov: ACGU→2 pairs, GCAU→2, AAUU→2, GGGAAAUCC→3; O(n³) DP verifiable byte-exact
SpliceAI (Jaganathan 2019)
AlphaFold-2 (Jumper 2021)
HMM (Rabiner 1989)
Smith-Waterman (1981)
Network biology (Barabasi-Oltvai 2004)
DeepSEA (Zhou 2015)
Needleman-Wunsch (1970)
Profile HMM (Krogh 1994)
PSI-BLAST (Altschul 1997)
Genome assembly (Pevzner 2001)
ML phylogeny (Felsenstein 1981)
AlphaFold2 (Jumper 2021)
Explore the computational-biology subtree on the interactive graph →