Preface.
BookOverview
Exercises
Errors
Acknowledgments
1BasicConceptsofMolecularBiology
1.1Life
1.2Proteins
1.3NucleicAcids
1.3.1DNA
1.3.2RNA
1.4TheMechanismsofMolecularGenetics
1.4.1GenesandtheGeneticCode
1.4.2Transcription,Translation,andProteinSynthesis
1.4.3JunkDNAandReadingFrames
1.4.4Chromosomes
1.4.5IstheGenomelikeaComputerProgram?
1.5HowtheGenomeIsStudied
1.5.1MapsandSequences
1.5.2SpecificTechniques
1.6TheHumanGenomeProject
1.7SequenceDatabases
Exercises
BibliographicNotes
2Strings,Graphs,andAlgorithms
2.1Strings
2.2Graphs
2.3Algorithms
Exercises
BibliographicNotes
3SequenceComparisonandDatabaseSearch
3.1BiologicalBackground
3.2ComparingTwoSequences
3.2.1GlobalComparison—TheBasicAlgorithm
3.2.2LocalComparison
3.2.3SemiglobalComparison
3.3ExtensionstotheBasicAlgorithms
3.3.1SavingSpace
3.3.2GeneralGapPenaltyFunctions
3.3.3AffineGapPenaltyFunctions
3.3.4ComparingSimilarSequences
3.4ComparingMultipleSequences
3.4.1TheSPMeasure
3.4.2StarAlignments
3.4.3TreeAlignments
3.5DatabaseSearch
3.5.1PAMMatrices
3.5.2BLAST
3.5.3FAST
3.6OtherIssues
*3.6.1SimilarityandDistance
3.6.2ParameterChoiceinSequenceComparison
3.6.3StringMatchingandExactSequenceComparison
Summary
Exercises
BibliographicNotes
4FragmentAssemblyofDNA
4.1BiologicalBackground
4.1.1TheIdealCase
4.1.2Complications
4.1.3AlternativeMethodsforDNASequencing
4.2Models
4.2.1ShortestCommonSuperstring
4.2.2Reconstruction
4.2.3Multicontig
*4.3Algorithms
4.3.1RepresentingOverlaps
4.3.2PathsOriginatingSuperstrings
4.3.3ShortestSuperstringsasPaths
4.3.4TheGreedyAlgorithm
4.3.5AcyclicSubgraphs
4.4Heuristics
4.4.1FindingOverlaps
Exercises
BibliographicNotes
5PhysicalMappingofDNA
5.1BiologicalBackground
5.1.1RestrictionSiteMapping
5.1.2HybridizationMapping
5.2Models
5.2.1RestrictionSiteModels
5.2.2IntervalGraphModels
5.2.3TheConsecutiveOnesProperty
5.2.4AlgorithmicImplications
5.3AnAlgorithmfortheC1PProblem
5.4AnApproximationforHybridizationMappingwithErrors
5.4.1AGraphModel
5.4.2AGuarantee
5.4.3ComputationalPractice
5.5HeuristicsforHybridizationMapping
5.5.1ScreeningChimericClones
5.5.2ObtainingaGoodProbeOrdering
Summary
Exercises
BibliographicNotes
6PhylogeneticTrees
6.1CharacterStatesandthePerfectPhylogenyProblem
6.2BinaryCharacterStates
6.3TwoCharacters
6.4ParsimonyandCompatibilityinPhylogenies
6.5AlgorithmsforDistanceMatrices
6.5.1ReconstructingAdditiveTrees
*6.5.2ReconstructingU!trametricTrees
6.6AgreementBetweenPhylogenies
Summary
Exercises
BibliographicNotes
7GenomeRearrangements
7.1BiologicalBackground
7.2OrientedBlocks
7.2.1Definitions
7.2.2Breakpoints
7.2.3TheDiagramofRealityandDesire
7.2.4InterleavingGraph
7.2.5BadComponents
7.2.6Algorithm
7.3UnorientedBlocks
7.3.1Strips
7.3.2Algorithm
Summary
Exercises
BibliographicNotes
8MolecularStructurePrediction
8.1RNASecondaryStructurePrediction
8.2TheProteinFoldingProblem
8.3ProteinThreading
Summary
Exercises
BibliographicNotes
9Epilogue:ComputingwithDNA
9.1TheHamiltonianPathProblem
9.2Satisfiability
9.3ProblemsandPromises
Exercises
BibliographicNotesandFurtherSources
AnswerstoSelectedExercises
References
Index...