Part VI. APPLICATIONS

Table of Contents

21. Bioinformatics
21.1. 21.1 Algorithms on sequences
21.1.1. 21.1.1 Distances of two sequences using linear gap penalty
21.1.2. 21.1.2 Dynamic programming with arbitrary gap function
21.1.3. 21.1.3 Gotoh algorithm for affine gap penalty
21.1.4. 21.1.4 Concave gap penalty
21.1.5. 21.1.5 Similarity of two sequences, the Smith-Waterman algorithm
21.1.6. 21.1.6 Multiple sequence alignment
21.1.7. 21.1.7 Memory-reduction with the Hirschberg algorithm
21.1.8. 21.1.8 Memory-reduction with corner-cutting
21.2. 21.2 Algorithms on trees
21.2.1. 21.2.1 The small parsimony problem
21.2.2. 21.2.2 The Felsenstein algorithm
21.3. 21.3 Algorithms on stochastic grammars
21.3.1. 21.3.1 Hidden Markov Models
21.3.2. 21.3.2 Stochastic context-free grammars
21.4. 21.4 Comparing structures
21.4.1. 21.4.1 Aligning labelled, rooted trees
21.4.2. 21.4.2 Co-emission probability of two HMMs
21.5. 21.5 Distance based algorithms for constructing evolutionary trees
21.5.1. 21.5.1 Clustering algorithms
21.5.2. 21.5.2 Neighbour joining
21.6. 21.6 Miscellaneous topics
21.6.1. 21.6.1 Genome rearrangement
21.6.2. 21.6.2 Shotgun sequencing
22. Computer Graphics
22.1. 22.1 Fundamentals of analytic geometry
22.1.1. 22.1.1 Cartesian coordinate system
22.2. 22.2 Description of point sets with equations
22.2.1. 22.2.1 Solids
22.2.2. 22.2.2 Surfaces
22.2.3. 22.2.3 Curves
22.2.4. 22.2.4 Normal vectors
22.2.5. 22.2.5 Curve modelling
22.2.6. 22.2.6 Surface modelling
22.2.7. 22.2.7 Solid modelling with blobs
22.2.8. 22.2.8 Constructive solid geometry
22.3. 22.3 Geometry processing and tessellation algorithms
22.3.1. 22.3.1 Polygon and polyhedron
22.3.2. 22.3.2 Vectorization of parametric curves
22.3.3. 22.3.3 Tessellation of simple polygons
22.3.4. 22.3.4 Tessellation of parametric surfaces
22.3.5. 22.3.5 Subdivision curves and meshes
22.3.6. 22.3.6 Tessellation of implicit surfaces
22.4. 22.4 Containment algorithms
22.4.1. 22.4.1 Point containment test
22.4.2. 22.4.2 Polyhedron-polyhedron collision detection
22.4.3. 22.4.3 Clipping algorithms
22.5. 22.5 Translation, distortion, geometric transformations
22.5.1. 22.5.1 Projective geometry and homogeneous coordinates
22.5.2. 22.5.2 Homogeneous linear transformations
22.6. 22.6 Rendering with ray tracing
22.6.1. 22.6.1 Ray surface intersection calculation
22.6.2. 22.6.2 Speeding up the intersection calculation
22.7. 22.7 Incremental rendering
22.7.1. 22.7.1 Camera transformation
22.7.2. 22.7.2 Normalizing transformation
22.7.3. 22.7.3 Perspective transformation
22.7.4. 22.7.4 Clipping in homogeneous coordinates
22.7.5. 22.7.5 Viewport transformation
22.7.6. 22.7.6 Rasterization algorithms
22.7.7. 22.7.7 Incremental visibility algorithms
23. Human-Computer Interaction
23.1. 23.1 Multiple-choice systems
23.1.1. 23.1.1 Examples of multiple-choice systems
23.2. 23.2 Generating multiple candidate solutions
23.2.1. 23.2.1 Generating candidate solutions with heuristics
23.2.2. 23.2.2 Penalty method with exact algorithms
23.2.3. 23.2.3 The linear programming—penalty method
23.2.4. 23.2.4 Penalty method with heuristics
23.3. 23.3 More algorithms for interactive problem solving
23.3.1. 23.3.1 Anytime algorithms
23.3.2. 23.3.2 Interactive evolution and generative design
23.3.3. 23.3.3 Successive fixing
23.3.4. 23.3.4 Interactive multicriteria decision making
23.3.5. 23.3.5 Miscellaneous