Algorithms on Strings, Trees and Sequences
alignmentsbioinformaticscomputational biologyDNA sequencingdynamic programmingedit distanceevolutionary treessequence databasesstring matchingsuffix trees
Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Analysis of algorithms and problem complexity (68Q25) Combinatorics on words (68R15) Computing methodologies for text processing; mathematical typography (68U15) Nonnumerical algorithms (68W05) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20)
Most traditional texts on algorithms in computer science contain one, perhaps two, principal chapters on techniques related to strings and sequences. This book is devoted entirely to these topics and for very good reason. The area of computational biology is hot, and the abstraction of DNA from a flexible three-dimensional molecule to a one-dimensional string opens the way for the use of powerful computing techniques to assist in the analysis of the structure and properties of these fundamental biological building blocks. So, unlike many computer science texts, the book is focused on applications to biology. Most algorithms presented are motivated by related biological problems. But at the same time the text is not just a ``how to manual on string and sequence analysis. A wide range of algorithms are rigorously presented along with correctness proofs and timing analyses. The author usually introduces a problem with a naive method for solving it, followed by repeatedly enhanced and sophisticated methods. Among the wide spectrum of techniques presented, most are illustrated with problems in current biological research. But many are chosen because of their potential application in future molecular biology. This stamps the book as ideal for computer scientists wishing to engage in the rapidly changing field of bioinformatics research. The author also points out that there will be many biologists and mathematicians with sufficient algorithmic background to read the book. The book includes all of the classic topics and most of the important advanced techniques in the field of string algorithms, with the exception of probabilistic methods (only lightly touched upon), parallel algorithms, theoretical results on algorithms for infinite alphabets and on algorithms that use only constant space, and machine learning stochastic-oriented methods. The text begins in Part I with the fundamental problem of exact string matching, starting with the Boyer-Moore and Knuth-Morris-Pratt algorithms, and then proceeding to variations including the Karp-Rabin fingerprint methods. Part II is devoted to suffix trees, a data structure that allows efficient solutions to a wide range of complex string problems. The suffix tree construction algorithms of Ukkonen, Weiner and McCreight are presented, followed by more than twenty applications, including a major section on lowest common ancestor retrieval. Part III covers the topics of inexact matching, sequence alignment and dynamic programming. The section begins with a detailed examination of the classic edit distance problem and continues with discussions of string similarity and alignment. Part III concludes with a chapter on the Holy Grail of multiple string comparison, one of the most important and active research areas in current biological sequence analysis, and a chapter on the building and searching of databases holding molecular sequence data. In Part IV the author branches out from well established techniques and from problems strictly defined on strings. He first discusses ``currents, being techniques that may lead to more powerful and effective methods, or techniques that may become less important as technology changes. He then discusses ``cousins, being problems, such as physical mapping, fragment assembly, and building phylogenetic trees, that, although related to string problems, are not themselves string problems. Finally he introduces a few important ``cameo topics, as well as topics that cross all three categories. The book concludes with a comprehensive bibliography containing almost 500 entries and, of particular use to Computer Scientists, a glossary composed predominantly of terms in molecular biology. This work is a timely contribution to the burgeoning research effort in computational biology. As the author himself points out,``Computer Science will make the most serious contribution to biology after the emergence of a large community of people who understand both fields and who know the strengths and needs of both. By drawing together such a wide range of applicable topics and presenting them in such a clear, motivational, and informative manner the author has contributed significantly to this effort and has provided an invaluable resource for graduate students and professional academics working, or intending to work, in the area of computational biology. The book could well be used as the basis for a graduate-level course, particularly as it contains over 400 exercises to reinforce presented material and to develop further topics. It is recommended most highly.
- Algorithms on Strings
- String algorithms. Papers based on the presentations at four meetings, London algorithms workshop, December 2000; London stringology day, February 2003; Rouen sequence algorithmics, June 2002; Patras stringology days, February 2004.
- scientific article; zbMATH DE number 828444
- Algorithmic aspects of bioinformatics. Translated from the German original
- Semi-local longest common subsequences in subquadratic time
- Quasi-median hulls in Hamming space are Steiner hulls
- On the tiling by translation problem
- Faster pattern matching with character classes using prime number encoding
- \(k\)-difference matching in amortized linear time for all the words in a text
- Linearized suffix tree: An efficient index data structure with the capabilities of suffix trees and suffix arrays
- Investigation of accelerated search for close text sequences with the help of vector representations
- A Lagrangian relaxation approach for the multiple sequence alignment problem
- Phylogenetic graph models beyond trees
- Discovering subword associations in strings in time linear in the output size
- Approximation algorithms for constrained generalized tree alignment problem
- Determining the consistency of partial tree descriptions
- Sparse LCS common substring alignment
- Computing the longest topological common subsequence of a symbol-wise totally ordered directed acyclic graph and a sequence
- Alignments with non-overlapping moves, inversions and tandem duplications in \(O(n^{4})\) time
- Repetitions in strings: algorithms and combinatorics
- Recognition of the structural-functional organization of genetic sequences
- Temporal similarity by measuring possibilistic uncertainty in CBR
- Faster entropy-bounded compressed suffix trees
- Searching for gapped palindromes
- Data compression for proof replay
- Average-optimal string matching
- A new method for approximate indexing and dictionary lookup with one error
- The greedy algorithm for edit distance with moves
- PRISM: an effective approach for frequent sequence mining via prime-block encoding
- Graph traversals, genes and matroids: An efficient case of the travelling salesman problem
- Parallel construction and query of index data structures for pattern matching on square matrices
- Approximate symbolic pattern matching for protein sequence data
- Non-approximability of weighted multiple sequence alignment.
- Generalizations of suffix arrays to multi-dimensional matrices.
- Finding approximate repetitions under Hamming distance.
- Truncated suffix trees and their application to data compression.
- Recent progress on selected topics in database research. -- A report by nine young Chinese researchers working in the United States.
- Combinatorics of periods in strings.
- Algorithmic complexity of protein identification: Combinatorics of weighted strings
- RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm.
- Hardness of approximation for non-overlapping local alignments.
- Distinguishing string selection problems.
- The shortest path problem with forbidden paths
- Approximation algorithms for the shortest total path length spanning tree problem
- Repetitive perhaps, but certainly not boring
- Fixed topology alignment with recombination
- Efficient data reconciliation
- Bounds for parametric sequence comparison
- On maximal repeats in strings
- Quasi-median graphs from sets of partitions
- Extended suffix array construction using Lyndon factors
- Improved upper bounds on all maximal -gapped repeats and palindromes
- A substring-substring LCS data structure
- Space-efficient indexes for forbidden extension queries
- Computing longest common extensions in partial words
- An improved approximation algorithm for the discrete Fréchet distance
- Fast structural alignment of biomolecules using a hash table, n-grams and string descriptors
- Approximate string matching with compressed indexes
- Suffix-sorting via Shannon-Fano-Elias codes
- A fast algorithm for the all-pairs suffix-prefix problem
- Exact solution to median surface problem using 3D graph search and application to parameter space exploration
- Border correlations, lattices, and the subgraph component polynomial
- Longest common extension
- Searching of gapped repeats and subrepetitions in a word
- On finding a longest common palindromic subsequence
- Tighter bounds and optimal algorithms for all maximal -gapped repeats and palindromes. Finding all maximal -gapped repeats and palindromes in optimal worst case time on integer alphabets
- On the number of gapped repeats with arbitrary gap
- Efficient algorithms for computing the inner edit distance of a regular language via transducers
- Hide and seek with repetitions
- A novel statistical measure for sequence comparison on the basis of \(k\)-word counts
- An efficient algorithm for LCS problem between two arbitrary sequences
- Edit distance with block deletions
- The smallest grammar problem as constituents choice and minimal grammar parsing
- Practical compressed suffix trees
- Sublinear time motif discovery from multiple sequences
- Modeling dynamic programming problems over sequences and trees with inverse coupled rewrite systems
- A faster quick search algorithm
- A new decomposition technique for maximal clique enumeration for sparse graphs
- \(xkcd\)-repeats: a new taxonomy of repeats defined by their context diversity
- Computing regularities in strings: a survey
- Computing the longest previous factor
- Exploiting word-level parallelism for fast convolutions and their applications in approximate string matching
- On-line construction of compact directed acyclic word graphs
- Linear time algorithms for finding and representing all the tandem repeats in a string
- Combinatorics and algorithms for low-discrepancy roundings of a real sequence
- Partial words and the critical factorization theorem
- Optimal, efficient reconstruction of root-unknown phylogenetic networks with constrained and structured recombination
- An inexact-suffix-tree-based algorithm for detecting extensible patterns
- Algorithms for pattern matching and discovery in RNA secondary structure
- Exact matching of RNA secondary structure patterns
- Ranked document retrieval for multiple patterns
- The suffix binary search tree and suffix AVL tree
- Reducing space for index implementation.
- Finding approximate palindromes in strings
- Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions
- Finding similar regions in many sequences
- Discovering instances of poetic allusion from anthologies of classical Japanese poems
- Tabular parsing and algebraic transformations
- The longest common subsequence problem for sequences with nested arc annotations.
- Approximate pattern matching and transitive closure logics.
- The haplotyping problem: an overview of computational models and solutions
- A space-efficient algorithm for sequence alignment with inversions and reversals
- Two-dimensional pattern matching with rotations
- Computing the similarity of two sequences with nested arc annotations
This page was built for publication: Algorithms on Strings, Trees and Sequences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4229812)
