An edition of BIOINFORMATICS ALGORITHMS,VOL.II (2015)

BIOINFORMATICS ALGORITHMS,VOL.II

by and

  • 1 Want to read
  • 1 Currently reading
Cover of: BIOINFORMATICS ALGORITHMS,VOL.II by Phillip Compeau, Pavel Pevzner, Phillip Compeau, Pavel Pevzner
Preview
Borrow

My Reading Lists:

Create a new list
Notes
  • 1 Want to read
  • 1 Currently reading
Notes

Check nearby libraries

Buy this book

Last edited by ImportBot
April 9, 2022 | History
Edit
An edition of BIOINFORMATICS ALGORITHMS,VOL.II (2015)

BIOINFORMATICS ALGORITHMS,VOL.II

by and

  • 1 Want to read
  • 1 Currently reading

This work doesn't have a description yet. Can you add one?

Publish Date
Publisher
Active Learning Publishers
Pages
320

Check nearby libraries

Buy this book

Subjects

Bioinformatics, Mathematics, Computational biology, Computer algorithms, Computational Biology, Algorithms, Bio-informatique, Mathématiques, Algorithmes
Edition Availability
Cover of: BIOINFORMATICS ALGORITHMS,VOL.II
BIOINFORMATICS ALGORITHMS,VOL.II
Jan 16, 2015, Active Learning Publishers
paperback

Add another edition?

Book Details

Table of Contents

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

Classifications

Library of Congress
QH324.2 .C6342 2015

The Physical Object

Format
paperback
Number of pages
320

Edition Identifiers

Open Library
OL36679120M
Internet Archive
bioinformaticsal0000comp
ISBN 10
0990374629
ISBN 13
9780990374626
LCCN
2015945208
OCLC/WorldCat
922937866

Work Identifiers

Work ID
OL27052843W

Source records

amazon.com record
Internet Archive item record

Community Reviews (0)

No community reviews have been submitted for this work.

Lists

Loading indicator
Loading carousel
Loading indicator
Loading carousel

History

Download catalog record: RDF / JSON
April 9, 2022 Edited by ImportBot import existing book
January 20, 2022 Created by ImportBot import new book