Algebraic and combinatorial computational biology

Cover
Algebraic and
Combinatorial
Computational Biology
Copyright
Contributors
Preface
1
Multiscale Graph-Theoretic Modeling of Biomolecular Structures
	Introduction
		The Molecules of Life
	Graph Theory Fundamentals
	Modeling RNA Structure
		RNA Secondary Structure Features
		Tree and Dual Graph Models of RNA Secondary Structure
			RNA Tree Graphs
			Using Graph Statistics to Understand RNA Secondary Structure
			RNA Dual Graphs
			Online RNA Resources
		Homework Problems and Projects
	RNA Structure and Matchings
		L&P Matchings
		The C&C Family
		Homework Problems and Projects
	Hierarchical Protein Models
		Weighted Graph Invariants
		Homework Problems and Projects
	References
	Further Reading
2
Tile-Based DNA Nanostructures
	Introduction
	Laboratory Process
	Graph Theoretical Formalism and Tools
		Flexible Tiles
		Flexible Tiles, Unconstrained Case
		Flexible Tiles, Constrained Case
		The Matrix of a Pot
	Rigid Tiles
	Computation by Self-Assembly
	Conclusion
	Resource Materials
	Acknowledgments
	References
	Further Reading
3
DNA rearrangements and graph polynomials
	Introduction
	Gene Assembly in Ciliates
		Biological Background
		Motivational Example
	Mathematical Preliminaries
	Mathematical Models for Gene Rearrangement
		Graphs Obtained From Double Occurrence Words
		Double Occurrence Words Corresponding to Graphs
	Graph Polynomials
		Transition Polynomial
		Assembly Polynomial
		Reduction Rules for the Assembly Polynomial
		Rearrangement Polynomial
	Generalizations
	Acknowledgments
	References
4
The Regulation of Gene Expression by Operons and the Local Modeling Framework
	Basic Biology Introduction
		The Central Dogma and Gene Regulation
		Types of Operons
		Two Well-Known Operons in E. coli
			The Lactose Operon
			The Arabinose Operon
	Continuous and Discrete Models of Biological Networks
		Differential Equation Models
		Bistability in Biological Systems
		Discrete Models of Biological Networks
	Local Models
		Polynomial Rings and Ideals for the Nonexpert
		Finite Fields
		Functions Over Finite Fields
		Boolean Networks and Local Models
		Asynchronous Boolean Networks and Local Models
		Phase Space Structure
	Local Models of Operons
		A Boolean Model of the lac Operon
		A Boolean Model of the ara Operon
	Analyzing Local Models With Computational Algebra
		Computing the Fixed Points
		Longer Limit Cycles
	Software for Local Models
		GINsim
		TURING: Algorithms for Computation With FDSs
	Concluding Remarks
	References
5
Modeling the Stochastic Nature of Gene Regulation With Boolean Networks
	Introduction
	Stochastic Discrete Dynamical Systems
	Long-Term Dynamics
	PageRank Algorithm
	Parameter Estimation Techniques
	Optimal Control for SDDS
		Control Actions
		Markov Decision Processes for SDDS
			Transition Probabilities
			Cost Function
			Optimal Control Policies
			Value Iteration Algorithm
	Discussion and Conclusions
	References
6
Inferring Interactions in Molecular Networks via Primary Decompositions of Monomial Ideals
	Introduction
		The Local Modeling Framework
		A Motivating Example of Reverse Engineering
	Stanley-Reisner Theory
		Monomial Ideals
		Square-Free Monomial Ideals
		Primary Decompositions
	Finding Min-Sets of Local Models
		Wiring Diagrams
		Feasible and Disposable Sets of Variables
		Min-Sets Over Non-Boolean Fields
	Finding Signed Min-Sets of Local Models
		The Pseudo-Monomial Ideal of Signed Nondisposable Sets
		A Non-Boolean Example
	Applications to a Real Gene Network
	Concluding Remarks
	References
7
Analysis of Combinatorial Neural Codes: An Algebraic Approach
	Introduction
		Biological Motivation: Neurons With Receptive Fields
		Receptive Field Relationships
		The Simplicial Complex of a Code
	The Neural Ideal
		Definition of the Neural Ideal
		The Neural Ideal and Receptive Field Relationships
	The Canonical Form
		Computing the Canonical Form
		Alternative Computation Method: The Primary Decomposition
		Sage Code for Computations
	Applications: Using the Neural Ideal
		Convex Realizability
		Dimension
	Concluding Remarks
	Acknowledgments
	References
	Further Reading
8
Predicting Neural Network Dynamics via Graphical Analysis
	Introduction
		Neuroscience Background and Motivation
		The CTLN Model
			Variety of Dynamics of CTLNs
	A CTLN as a Patchwork of Linear Systems
		How Graph Structure Affects Fixed Points
	Graphical Analysis of Stable and Unstable Fixed Points
		Graph Theory Concepts
		Stable Fixed Points
			Opening Exploration: Stable Fixed Point Supports
		Unstable Fixed Points
			Parity
			Sinks and Sources
			Uniform In-Degree Subgraphs
			Domination
			Using the Rules to Compute FP(G)
	Predicting Dynamic Attractors via Graph Structure
		Matlab Exploration: Sequences of Attractors
		Sequence Prediction Algorithm
		Symmetry of Graphs Acting on the Space of Attractors
	Acknowledgments
	Review of Linear Systems of ODEs
	References
9
Multistationarity in Biochemical Networks: Results, Analysis, and Examples
	Introduction
	Reaction Network Terminology and Background
		Chemical Reaction Networks and Their Dynamics
		Some Useful Notation
		The Jacobian Matrix
		Stoichiometry Classes
		Equilibria
		Nondegenerate Equilibria
		The Reduced Jacobian
		General Setup and Preliminaries
	Necessary Conditions for Multistationarity I: Injective CRNs
	Necessary Conditions for Multistationarity II: The DSR Graph
	Sufficient Conditions for Multistationarity: Inheritance of Multiple Equilibria
	Sufficient Conditions for Multistationarity II: The Determinant Optimization Method
	Results Based on Deficiency Theory
		The Deficiency Zero and Deficiency One Theorems
		The Deficiency One Algorithm and the Advanced Deficiency Algorithm
	Acknowledgments
	References
10
Polytopes and Linear Programming for Phylogenetics
	Introduction
		Phylogenetic Reconstructions and Interpretation
		Balanced Minimum Evolution
		Definitions and Notation
	Polytopes and Relaxations
		What Is a Polytope?
		The BME Polytope
		The Splitohedron
	Optimizing With Linear Programming
		Discrete Integer Linear Programming: The Branch and Bound Algorithm
		Recursive Structure: Branch Selection Strategy and Fixing Values
		Pseudocode for the Algorithm: PolySplit
	Neighbor Joining and Edge Walking
		NNI and SPR Moves, and FastMe 2.0
	Summary
	References
11
Data Clustering and Self-Organizing Maps in Biology
	Clustering: An Introduction
	Clustering: A Basic Procedure
		Data Representation
		Clustering Algorithm Selection
		Cluster Validation
		Interpretation of Results
	Types of Clustering
		Hard Clustering
			Partitional Clustering
			Hierarchical Clustering
		Exercises
	Fuzzy Clustering
	Self-Organizing Maps
	SOM Applications to Biological Data
		Example 1: Water Composition Data
		Example 2: Grasshopper Size Data
		Group Project: Iris Data Set
	References
12
Toward Revealing Protein Function: Identifying Biologically Relevant Clusters With Graph Spectral Methods
	Introduction to Proteins
		Protein Structures
		Experimental Determination of Protein Structure
		Isofunctional Families
		Sequence Motifs and Logos
	Clustering of Data
		An Overview
		Clustering Methods
		Network Spectral Methods
		Spectral Clustering
		Spectral Clustering With Outliers
	Clustering to Identify Isofunctional Families
		Similarity Scores Based on Tertiary Structure
	References
Index
	A
	B
	C
	D
	E
	F
	G
	H
	I
	J
	K
	L
	M
	N
	O
	P
	Q
	R
	S
	T
	U
	V
	W
	X
Back Cover