BIOINFORMATICS ALGORITHMS,VOL.II
Publisher: Active Learning Publishers
Published: Jan 16, 2015
Format: paperback
Number of pages: 320
ISBN-13: 9780990374626
Table of contents: title: List of Code Challenges
pagenum: xviii; title: About the Textbook
pagenum: xxi; title: Meet the Authors
pagenum: xxi; title: Meet the Development Team
pagenum: xxii; title: Acknowledgments
pagenum: xxiii; label: 1
title: Where in the Genome Does DNA Replication Begin?
pagenum: 2; title: A Journey of a Thousand Miles
pagenum: 3; title: Hidden Messages in the Replication Origin
pagenum: 5; title: DnaA Boxes
pagenum: 5; title: Hidden Messages in "The Gold-Bug"
pagenum: 6; title: Counting Words
pagenum: 7; title: The Frequent Words Problem
pagenum: 8; title: Frequent Words in Vibrio cholerae
pagenum: 10; title: Some Hidden Messages are More Surprising than Others
pagenum: 11; title: An Explosion of Hidden Messages
pagenum: 13; title: Looking for Hidden Messages in Multiple Genomes
pagenum: 13; title: The Clump Finding Problem
pagenum: 14; title: The Simplest Way to Replicate DNA
pagenum: 16; title: Asymmetry of Replication
pagenum: 18; title: Peculiar Statistics of the Forward and Reverse Half-Strands
pagenum: 22; title: Deamination
pagenum: 22; title: The Skew Diagram
pagenum: 23; title: Some Hidden Messages are More Elusive than Others
pagenum: 26; title: A Final Attempt at Finding DnaA Boxes in E. coli
pagenum: 29; title: Epilogue: Complications in oriC Predictions
pagenum: 31; title: Open Problems
pagenum: 33; title: Multiple Replication Origins in a Bacterial Genome
pagenum: 33; title: Finding Replication Origins in Archaea
pagenum: 35; title: Finding Replication Origins in Yeast
pagenum: 36; title: Computing Probabilities of Patterns in a String
pagenum: 37; title: Charging Stations
pagenum: 39; title: The Frequency Array
pagenum: 39; title: Converting Patterns to Numbers and Vice-Versa
pagenum: 41; title: Finding Frequent Words by Sorting
pagenum: 43; title: Solving the Clump Finding Problem
pagenum: 44; title: Solving the Frequent Words with Mismatches Problem
pagenum: 47; title: Generating the Neighborhood of a String
pagenum: 49; title: Finding Frequent Words with Mismatches by Sorting
pagenum: 51; title: Detours
pagenum: 52; title: Big-O Notation
pagenum: 52; title: Probabilities of Patterns in a String
pagenum: 52; title: The Most Beautiful Experiment in Biology
pagenum: 57; title: Directionality of DNA Strands
pagenum: 59; title: The Towers of Hanoi
pagenum: 60; title: The Overlapping Words Paradox
pagenum: 62; title: Bibliography Notes
pagenum: 64; label: 2
title: Which DNA Patterns Play the Role of Molecular Clocks?
pagenum: 66; title: Do We Have a "Clock" Gene?
pagenum: 67; title: Motif Finding Is More Difficult Than You Think
pagenum: 68; title: Identifying the Evening Element
pagenum: 68; title: Hide and Seek with Motifs
pagenum: 69; title: A Brute Force Algorithm for Motif Finding
pagenum: 71; title: Scoring Motifs
pagenum: 72; title: From Motifs to Profile Matrices and Consensus Strings
pagenum: 72; title: Towards a More Adequate Motif Scoring Function
pagenum: 75; title: Entropy and the Motif Logo
pagenum: 76; title: From Motif Finding to Finding a Median String
pagenum: 77; title: The Motif Finding Problem
pagenum: 77; title: Reformulating the Motif Finding Problem
pagenum: 77; title: The Median String Problem
pagenum: 80; title: Why Have We Reformulated the Motif Finding Problem?
pagenum: 82; title: Greedy Motif Search
pagenum: 83; title: Using the Profile Matrix to Roll Dice
pagenum: 83; title: Analyzing Greedy Motif Finding
pagenum: 85; title: Motif Finding Meets Oliver Cromwell
pagenum: 86; title: What Is the Probability That the Sun Will Not Rise Tomorrow?
pagenum: 86; title: Laplace's Rule of Succession
pagenum: 87; title: An Improved Greedy Motif Search
pagenum: 88; title: Randomized Motif Search
pagenum: 91; title: Rolling Dice to Find Motifs
pagenum: 91; title: Why Randomized Motif Search Works
pagenum: 93; title: How Can a Randomized Algorithm Perform So Well?
pagenum: 96; title: Gibbs Sampling
pagenum: 98; title: Gibbs Sampling in Action
pagenum: 100; title: Epilogue: How Does Tuberculosis Hibernate to Hide from Antibiotics?
pagenum: 104; title: Charging Stations
pagenum: 107; title: Solving the Median String Problem
pagenum: 107; title: Detours
pagenum: 108; title: Gene Expression
pagenum: 108; title: DNA Arrays
pagenum: 108; title: Buffon's Needle
pagenum: 109; title: Complications in Motif Finding
pagenum: 112; title: Relative Entropy
pagenum: 112; title: Bibliography Notes
pagenum: 115; label: 3
title: How Do We Assemble Genomes?
pagenum: 115; title: Exploding Newspapers
pagenum: 117; title: The String Reconstruction Problem
pagenum: 120; title: Genome Assembly Is More Difficult Than You Think
pagenum: 120; title: Reconstructing Strings from k-mers
pagenum: 120; title: Repeats Complicate Genome Assembly
pagenum: 123; title: String Reconstruction as a Walk in the Overlap Graph
pagenum: 124; title: From a String to a Graph
pagenum: 124; title: The Genome Vanishes
pagenum: 127; title: Two Graph Representations
pagenum: 129; title: Hamiltonian Paths and Universal Strings
pagenum: 130; title: Another Graph for String Reconstruction
pagenum: 131; title: Gluing Nodes and de Bruijn Graphs
pagenum: 131; title: Walking in the de Bruijn Graph
pagenum: 134; title: Eulerian Paths
pagenum: 134; title: Another Way to Construct de Bruijn Graphs
pagenum: 135; title: Constructing de Bruijn Graphs from k-mer Composition
pagenum: 137; title: De Bruijn Graphs Versus Overlap Graphs
pagenum: 138; title: The Seven Bridges of Königsberg
pagenum: 139; title: Euler's Theorem
pagenum: 142; title: From Euler's Theorem to an Algorithm for Finding Eulerian Cycles
pagenum: 146; title: Constructing Eulerian Cycles
pagenum: 146; title: From Eulerian Cycles to Eulerian Paths
pagenum: 146; title: Constructing Universal Strings
pagenum: 147; title: Assembling Genomes from Read-Pairs
pagenum: 150; title: From Reads to Read-Pairs
pagenum: 150; title: Transforming Read-Pairs into Long Virtual Reads
pagenum: 151; title: From Composition to Paired Composition
pagenum: 153; title: Paired de Bruijn Graphs
pagenum: 154; title: A Pitfall of Paired de Bruijn Graphs
pagenum: 155; title: Epilogue: Genome Assembly Faces Real Sequencing Data
pagenum: 158; title: Breaking Reads into k-mers
pagenum: 158; title: Splitting the Genome into Contigs
pagenum: 159; title: Assembling Error-Prone Reads
pagenum: 161; title: Inferring Multiplicities of Edges in de Bruijn Graphs
pagenum: 162; title: Charging Stations
pagenum: 164; title: The Effect of Gluing on the Adjacency Matrix
pagenum: 164; title: Generating All Eulerian Cycles
pagenum: 165; title: Reconstructing a String Spelled by a Path in the Paired de Bruijn Graph
pagenum: 166; title: Maximal Non-Branching Paths in a Graph
pagenum: 169; title: Detours
pagenum: 170; title: A Short History of DNA Sequencing Technologies
pagenum: 170; title: Repeats in the Human Genome
pagenum: 172; title: Graphs
pagenum: 173; title: The Icosian Game
pagenum: 175; title: Tractable and Intractable Problems
pagenum: 176; title: From Euler to Hamilton to de Bruijn
pagenum: 177; title: The Seven Bridges of Kaliningrad
pagenum: 178; title: The BEST Theorem
pagenum: 179; title: Bibliography Notes
pagenum: 180; label: 4
title: How Do We Sequence Antibiotics?
pagenum: 182; title: The Discovery of Antibiotics
pagenum: 183; title: How Do Bacteria Make Antibiotics?
pagenum: 184; title: How Peptides Are Encoded by the Genome
pagenum: 184; title: Where Is Tyrocidine Encoded in the Bacillus brevis Genome?
pagenum: 186; title: From Linear to Cyclic Peptides
pagenum: 188; title: Dodging the Central Dogma of Molecular Biology
pagenum: 188; title: Sequencing Antibiotics by Shattering Them into Pieces
pagenum: 190; title: Introduction to Mass Spectrometry
pagenum: 190; title: The Cyclopeptide Sequencing Problem
pagenum: 191; title: A Brute Force Algorithm for Cyclopeptide Sequencing
pagenum: 193; title: A Branch-and-Bound Algorithm for Cyclopeptide Sequencing
pagenum: 194; title: Mass Spectrometry Meets Golf
pagenum: 197; title: From Theoretical to Real Spectra
pagenum: 197; title: Adapting Cyclopeptide Sequencing for Spectra with Errors
pagenum: 198; title: From 20 to More than 100 Amino Acids
pagenum: 201; title: The Spectral Convolution Saves the Day
pagenum: 203; title: Epilogue: From Simulated to Real Spectra
pagenum: 205; title: Open Problems
pagenum: 208; title: The Beltway and Turnpike Problems
pagenum: 208; title: Sequencing Cyclic Peptides in Primates
pagenum: 209; title: Charging Stations
pagenum: 211; title: Generating the Theoretical Spectrum of a Peptide
pagenum: 211; title: How Fast Is CyclopeptideSequencing?
pagenum: 212; title: Trimming the Peptide Leaderboard
pagenum: 214; title: Detours
pagenum: 215; title: Gause and Lysenkoism
pagenum: 215; title: Discovery of Codons
pagenum: 216; title: Quorum Sensing
pagenum: 217; title: Molecular Mass
pagenum: 217; title: Selenocysteine and Pyrrolysine
pagenum: 218; title: Pseudo-Polynomial Algorithm for the Turnpike Problem
pagenum: 219; title: Split Genes
pagenum: 220; title: Bibliography Notes
pagenum: 221; label: 5
title: How Do We Compare Biological Sequences?
pagenum: 222; title: Cracking the Non-Ribosomal Code
pagenum: 223; title: The RNA Tie Club
pagenum: 223; title: From Protein Comparison to the Non-Ribosomal Code
pagenum: 224; title: What Do Oncogenes and Growth Factors Have in Common?
pagenum: 225; title: Introduction to Sequence Alignment
pagenum: 226; title: Sequence Alignment as a Game
pagenum: 226; title: Sequence Alignment and the Longest Common Subsequence
pagenum: 227; title: The Manhattan Tourist Problem
pagenum: 229; title: What Is the Best Sightseeing Strategy?
pagenum: 229; title: Sightseeing in an Arbitrary Directed Graph
pagenum: 232; title: Sequence Alignment Is the Manhattan Tourist Problem in Disguise
pagenum: 233; title: An Introduction to Dynamic Programming: The Change Problem
pagenum: 236; title: Changing Money Greedily
pagenum: 236; title: Changing Money Recursively
pagenum: 237; title: Changing Money Using Dynamic Programming
pagenum: 239; title: The Manhattan Tourist Problem Revisited
pagenum: 241; title: From Manhattan to an Arbitrary Directed Acyclic Graph
pagenum: 245; title: Sequence Alignment as Building a Manhattan-like Graph
pagenum: 245; title: Dynamic Programming in an Arbitrary DAG
pagenum: 246; title: Topological Orderings
pagenum: 247; title: Backtracking in the Alignment Graph
pagenum: 251; title: Scoring Alignments
pagenum: 253; title: What Is Wrong with the LCS Scoring Model?
pagenum: 253; title: Scoring Matrices
pagenum: 254; title: From Global to Local Alignment
pagenum: 255; title: Global Alignment
pagenum: 255; title: Limitations of Global Alignment
pagenum: 257; title: Free Taxi Rides in the Alignment Graph
pagenum: 259; title: The Changing Faces of Sequence Alignment
pagenum: 261; title: Edit Distance
pagenum: 261; title: Fitting Alignment
pagenum: 263; title: Overlap Alignment
pagenum: 263; title: Penalizing Insertions and Deletions in Sequence Alignment
pagenum: 264; title: Affine Gap Penalties
pagenum: 264; title: Building Manhattan on Three Levels
pagenum: 266; title: Space-Efficient Sequence Alignment
pagenum: 269; title: Computing Alignment Score Using Linear Memory
pagenum: 269; title: The Middle Node Problem
pagenum: 270; title: A Surprisingly Fast and Memory-Efficient Alignment Algorithm
pagenum: 273; title: The Middle Edge Problem
pagenum: 275; title: Epilogue: Multiple Sequence Alignment
pagenum: 277; title: Building a Three-Dimensional Manhattan
pagenum: 277; title: A Greedy Multiple Alignment Algorithm
pagenum: 280; title: Detours
pagenum: 282; title: Fireflies and the Non-Ribosomal Code
pagenum: 282; title: Finding a Longest Common Subsequence without Building a City
pagenum: 283; title: Constructing a Topological Ordering
pagenum: 284; title: PAM Scoring Matrices
pagenum: 285; title: Divide-and-Conquer Algorithms
pagenum: 287; title: Scoring Multiple Alignments
pagenum: 289; title: Bibliography Notes
pagenum: 291; label: 6
title: Are There Fragile Regions in the Human Genome?
pagenum: 292; title: Of Mice and Men
pagenum: 293; title: How Different Are the Human and Mouse Genomes?
pagenum: 293; title: Synteny Blocks
pagenum: 294; title: Reversals
pagenum: 294; title: Rearrangement Hotspots
pagenum: 295; title: The Random Breakage Model of Chromosome Evolution
pagenum: 297; title: Sorting by Reversals
pagenum: 299; title: A Greedy Heuristic for Sorting by Reversals
pagenum: 304; title: Breakpoints
pagenum: 306; title: What Are Breakpoints?
pagenum: 306; title: Counting Breakpoints
pagenum: 307; title: Sorting by Reversals as Breakpoint Elimination
pagenum: 308; title: Rearrangements in Tumor Genomes
pagenum: 310; title: From Unichromosomal to Multichromosomal Genomes
pagenum: 311; title: Translocations, Fusions, and Fissions
pagenum: 311; title: From a Genome to a Graph
pagenum: 313; title: 2-Breaks
pagenum: 314; title: Breakpoint Graphs
pagenum: 316; title: Computing the 2-Break Distance
pagenum: 320; title: Rearrangement Hotspots in the Human Genome
pagenum: 323; title: The Random Breakage Model Meets the 2-Break Distance Theorem
pagenum: 323; title: The Fragile Breakage Model
pagenum: 324; title: Epilogue: Synteny Block Construction
pagenum: 325; title: Genomic Dot-Plots
pagenum: 325; title: Finding Shared k-mers
pagenum: 326; title: Constructing Synteny Blocks from Shared k-mers
pagenum: 329; title: Synteny Blocks as Connected Components in Graphs
pagenum: 331; title: Open Problem: Can Rearrangements Shed Light on Bacterial Evolution?
pagenum: 333; title: Charging Stations
pagenum: 335; title: From Genomes to the Breakpoint Graph
pagenum: 335; title: Solving the 2-Break Sorting Problem
pagenum: 338; title: Detours
pagenum: 340; title: Why Is the Gene Content of Mammalian X Chromosomes so Conserved?
pagenum: 340; title: Discovery of Genome Rearrangements
pagenum: 340; title: The Exponential Distribution
pagenum: 341; title: Bill Gates and David X. Cohen Flip Pancakes
pagenum: 342; title: Sorting Linear Permutations by Reversals
pagenum: 343; title: Bibliography Notes
pagenum: 346; title: Bibliography
pagenum: 349; title: Image Courtesies
pagenum: 355; title: List of Code Challenges (detailed)
pagenum: xvii; label: Chapter 1
pagenum: 2; label: (1A)
title: Compute the Number of Times a Pattern Appears in a Text
pagenum: 8; label: (1B)
title: Find the Most Frequent Words in a String
pagenum: 8; label: (1C)
title: Find the Reverse Complement of a DNA String
pagenum: 12; label: (1D)
title: Find All Occurrences of a Pattern in a String
pagenum: 13; label: (1E)
title: Find Patterns Forming Clumps in a String
pagenum: 15; label: (1F)
title: Find a Position in a Genome Minimizing the Skew
pagenum: 25; label: (1G)
title: Compute the Hamming Distance Between Two Strings
pagenum: 27; label: (1H)
title: Find All Approximate Occurrences of a Pattern in a String
pagenum: 27; label: (1I)
title: Find the Most Frequent Words with Mismatches in a String
pagenum: 28; label: (1J)
title: Find Frequent Words with Mismatches and Reverse Complements
pagenum: 29; label: (1K)
title: Generate the Frequency Array of a String
pagenum: 40; label: (1L)
title: Implement PatternToNumber
pagenum: 42; label: (1M)
title: Implement NumberToPattern
pagenum: 43; label: (1N)
title: Generate the d-Neighborhood of a String
pagenum: 50; label: Chapter 2
pagenum: 66; label: (2A)
title: Implement MotifEnumeration
pagenum: 71; label: (2B)
title: Find a Median String
pagenum: 81; label: (2C)
title: Find a Profile-most Probable k-mer in a String
pagenum: 85; label: (2D)
title: Implement GreedyMotifSearch
pagenum: 85; label: (2E)
title: Implement GreedyMotifSearch with Pseudocounts
pagenum: 91; label: (2F)
title: Implement RandomizedMotifSearch
pagenum: 93; label: (2G)
title: Implement GibbsSampler
pagenum: 100; label: (2H)
title: Implement DistanceBetweenPatternAndStrings
pagenum: 107; label: Chapter 3
pagenum: 115; label: (3A)
title: Generate the k-mer Composition of a String
pagenum: 120; label: (3B)
title: Reconstruct a String from its Genome Path
pagenum: 125; label: (3C)
title: Construct the Overlap Graph of a Collection of k-mers
pagenum: 128; label: (3D)
title: Construct the de Bruijn Graph of a String
pagenum: 132; label: (3E)
title: Construct the de Bruijn Graph of a Collection of k-mers
pagenum: 137; label: (3F)
title: Find an Eulerian Cycle in a Graph
pagenum: 146; label: (3G)
title: Find an Eulerian Path in a Graph
pagenum: 147; label: (3H)
title: Reconstruct a String from its k-mer Composition
pagenum: 147; label: (3I)
title: Find a k-Universal Circular String
pagenum: 148; label: (3J)
title: Reconstruct a String from its Paired Composition
pagenum: 157; label: (3K)
title: Generate the Contigs from a Collection of Reads
pagenum: 160; label: (3L)
title: Construct a String Spelled by a Gapped Genome Path
pagenum: 169; label: (3M)
title: Generate All Maximal Non-Branching Paths in a Graph
pagenum: 169; label: Chapter 4
pagenum: 182; label: (4A)
title: Translate an RNA String into an Amino Acid String
pagenum: 186; label: (4B)
title: Find Substrings of a Genome Encoding a Given Amino Acid String
pagenum: 187; label: (4C)
title: Generate the Theoretical Spectrum of a Cyclic Peptide
pagenum: 191; label: (4D)
title: Compute the Number of Peptides of Given Total Mass
pagenum: 193; label: (4E)
title: Find a Cyclic Peptide with Theoretical Spectrum Matching an Ideal Spectrum
pagenum: 196; label: (4F)
title: Compute the Score of a Cyclic Peptide Against a Spectrum
pagenum: 198; label: (4G)
title: Implement LeaderboardCyclopeptideSequencing
pagenum: 200; label: (4H)
title: Generate the Convolution of a Spectrum
pagenum: 203; label: (4I)
title: Implement ConvolutionCyclopeptideSequencing
pagenum: 205; label: (4J)
title: Generate the Theoretical Spectrum of a Linear Peptide
pagenum: 211; label: (4K)
title: Compute the Score of a Linear Peptide
pagenum: 214; label: (4L)
title: Implement Trim to Trim a Peptide Leaderboard
pagenum: 215; label: (4M)
title: Solve the Turnpike Problem
pagenum: 219; label: Chapter 5
pagenum: 222; label: (5A)
title: Find the Minimum Number of Coins Needed to Make Change
pagenum: 240; label: (5B)
title: Find the Length of a Longest Path in a Manhattan-like Grid
pagenum: 245; label: (5C)
title: Find a Longest Common Subsequence of Two Strings
pagenum: 252; label: (5D)
title: Find the Longest Path in a DAG
pagenum: 253; label: (5E)
title: Find a Highest-Scoring Alignment of Two Strings
pagenum: 255; label: (5F)
title: Find a Highest-Scoring Local Alignment of Two Strings
pagenum: 260; label: (5G)
title: Compute the Edit Distance Between Two Strings
pagenum: 262; label: (5H)
title: Find a Highest-Scoring Fitting Alignment of Two Strings
pagenum: 263; label: (5I)
title: Find a Highest-Scoring Overlap Alignment of Two Strings
pagenum: 264; label: (5J)
title: Align Two Strings Using Affine Gap Penalties
pagenum: 268; label: (5K)
title: Find a Middle Edge in an Alignment Graph in Linear Space
pagenum: 275; label: (5L)
title: Align Two Strings Using Linear Space
pagenum: 276; label: (5M)
title: Construct a Highest-Scoring Multiple Alignment
pagenum: 279; label: (5N)
title: Find a Topological Ordering of a DAG
pagenum: 285; label: Chapter 6
pagenum: 292; label: (6A)
title: Implement GreedySorting to Sort a Permutation by Reversals
pagenum: 305; label: (6B)
title: Compute the Number of Breakpoints in a Permutation
pagenum: 308; label: (6C)
title: Compute the 2-Break Distance Between a Pair of Genomes
pagenum: 321; label: (6D)
title: Find a Shortest Transformation of a Genome into Another by 2-Breaks
pagenum: 322; label: (6E)
title: Find All Shared k-mers of a Pair of Strings
pagenum: 326; label: (6F)
title: Implement ChromosomeToCycle
pagenum: 336; label: (6G)
title: Implement CycleToChromosome
pagenum: 337; label: (6H)
title: Implement ColoredEdges
pagenum: 337; label: (6I)
title: Implement GraphToGenome
pagenum: 338; label: (6J)
title: Implement 2-BreakOnGenomeGraph
pagenum: 339; label: (6K)
title: Implement 2-BreakOnGenome
pagenum: 339