Algorithms_on_String_Trees_and_Sequences-libre.pdf下载分享

资料简介

《Algorithms on Strings, Trees and Sequences》一书深入探讨了精确和不精确的字符串匹配算法，涵盖了Boyer-Moore、Knuth-Morris-Pratt等经典方法以及现代的半数值匹配技术。本书适合计算机科学与计算生物学领域的研究人员和技术人员。

• 文件名称：Algorithms_on_String_Trees_and_Sequences-libre.pdf

• 文件类型：PDF文档

• 文件标签：字符串匹配、生物信息学、动态规划

内容预览

Algorithms on Strings, Trees,
and Sequences
COMPUTER SCIENCE AND COMPUTATIONAL
BIOLOGY
Dan Gusfield
University of California, Davis
CAMBRIDGE
UNIVERSITY PRESS

Contents
Preface
xiii
I Exact String Matching: The Fundamental String Problem
1 Exact Matching: Fundamental Preprocessing and First Algorithms
1.1 The naive method
1.2 The preprocessing approach
1.3 Fundamental preprocessing of the pattern
1.4 Fundamental preprocessing in linear time
1.5 The simplest linear-time exact matching algorithm
1.6 Exercises
2 Exact Matching: Classical Comparison-Based Methods
2.1
Introduction
2.2 The Boyer-Moore Algorithm
2.3
The Knuth-Morris-Pratt algorithm
2.4 Real- time string matching
2.5 Exercises
3 Exact Matching: A Deeper Look at Classical Methods
3.1
A Boyer-Moore variant with a "simple" linear time bound
3.2 Cole's linear worst-case bound for Boyer-Moore
3.3
The original preprocessing for Knuth-Momis-Pratt
3.4
Exact matching with a set of patterns
3.5 Three applications of exact set matching
3.6
Regular expression pattern matching
3.7
Exercises
4 Seminumerical String Matching
4.1
Arithmetic versus comparison-based methods
4.2 The Shift-And method
4.3 The match-count problem and Fast Fourier Transform
4.4 Karp-Rabin fingerprint methods for exact match
4.5 Exercises

CONTENTS
8.10
For the purists: how to avoid bit-level operations
8.11
Exercises
9 More Applications of Suffix Trees
Longest common extension: a bridge to inexact matching
Finding all maximal palindromes in linear time
Exact matching with wild cards
The k-mismatch problem
Approximate palindromes and repeats
Faster methods for tandem repeats
A linear-time solution to the multiple common substring-problem
Exercises
IIIInexact Matching, Sequence Alignment, Dynamic Programming
10 The Importance of (Sub)sequence Comparison in Molecular Biology
11 Core String Edits, Alignments, and Dynamic Programming
Introduction
The edit distance between two strings
Dynamic programming calculation of edit distance
Edit graphs
Weighted edit distance
String similarity
Local alignment: finding substrings of high similarity
Gaps
Exercises
12 Refining Core String Edits and Alignments
12.1 Computing alignments in only linear space
12.2
Faster algorithms when the number of differences are bounded
12.3
Exclusion methods: fast expected running time
12.4
Yet more suffix trees and more hybrid dynamic programming
12.5
A faster (combinatorial) algorithm for longest common subsequence
12.6 Convex gap weights
12.7
The Four-Russians speedup
12.8
Exercises
13 Extending the Core Problems
13.1
Parametric sequence alignment
13.2
Computing suboptimal alignments
13.3
Chaining diverse local alignments
13.4
Exercises
14 Multiple String Comparison - The Holy Grail
14.1
Why multiple string comparison?
14.2
Three "big-picture" biological uses for multiple string comparison
14.3
Family and superfamily representation

viii
CONTENTS
II Suffix Tees and Their Uses
5 Introduction to Suffix Trees
5.1
A short history
5.2
Basic definitions
5.3
A motivating example
5.4 A naive algorithm to build a suffix tree
6 Linear-Time Constructio...