Algorithms on Strings, Trees and Sequences
From MaRDI portal
Publication:4229812
DOI10.1017/CBO9780511574931zbMath0934.68103OpenAlexW938539187WikidataQ55980413 ScholiaQ55980413MaRDI QIDQ4229812
Publication date: 28 February 1999
Full work available at URL: https://doi.org/10.1017/cbo9780511574931
dynamic programmingbioinformaticsstring matchingevolutionary treescomputational biologyedit distanceDNA sequencingsuffix treesalignmentssequence databases
Analysis of algorithms and problem complexity (68Q25) Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Nonnumerical algorithms (68W05) Combinatorics on words (68R15) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Computing methodologies for text processing; mathematical typography (68U15)
Related Items
Polynomial-time approximation algorithms for weighted LCS problem, Models and algorithms for competitive facility location problems with different customer behavior, On del-robust primitive words, Finding the leftmost critical factorization on unordered alphabet, Longest common extensions in trees, FM-index of alignment: a compressed index for similar strings, Linear-size suffix tries, DCA based algorithms for multiple sequence alignment (MSA), A multiobjective optimization algorithm for the weighted LCS, The power of greedy algorithms for approximating Max-ATSP, cyclic cover, and superstrings, Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations, Construct, Merge, Solve \& Adapt A new general algorithm for combinatorial optimization, Non-expandable non-overlapping sets of pictures, String-matching with OBDDs, Combined super-/substring and super-/subsequence problems, Compressed directed acyclic word graph with application in local alignment, \textsc{FlipCut} supertrees: towards matrix representation accuracy in polynomial time, Palindrome pattern matching, Versatile string kernels, A probabilistic PTAS for shortest common superstring, Facility layout based on sequence analysis: design of flowshops, On-line construction of position heaps, On parsing optimality for dictionary-based text compression -- the \texttt{Zip} case, The structural border array, Algorithms for path-constrained sequence alignment, The longest common extension problem revisited and applications to approximate string searching, Reverse engineering of compact suffix trees and links: a novel algorithm, A subquadratic algorithm for minimum palindromic factorization, A global averaging method for dynamic time warping, with applications to clustering, Counting distinct palindromes in a word in linear time, An algorithm for mapping short reads to a dynamically changing genomic sequence, Searching for smallest grammars on large sequences and application to DNA, On-line suffix tree construction with reduced branching, Towards a theory of patches, Ultra-succinct representation of ordered trees with applications, Fast, practical algorithms for computing all the repeats in a string, A new algorithm for aligning nested arc-annotated sequences under arbitrary weight schemes, Approximate all-pairs suffix/prefix overlaps, Linear-time construction of two-dimensional suffix trees, A sum-over-paths extension of edit distances accounting for all sequence alignments, Efficient retrieval of approximate palindromes in a run-length encoded string, Quadratic-time algorithm for a string constrained LCS problem, PSIST: a scalable approach to indexing protein structures using suffix trees, A parallel strategy for biological sequence alignment in restricted memory space, PCB assembly scheduling with alternative nozzle types for one component type, Parameterized longest previous factor, Efficient chaining of seeds in ordered trees, Efficiency issues in the KBMAG procedure, Graph clustering, Comparing and aggregating partially resolved trees, Textual data compression in computational biology: algorithmic techniques, Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. I. Reconstruction without forbidden words, The pseudopalindromic completion of regular languages, A PTAS for the square tiling problem, A simple yet time-optimal and linear-space algorithm for shortest unique substring queries, Alphabet-independent algorithms for finding context-sensitive repeats in linear time, \(k\)-abelian pattern matching, On the generalized constrained longest common subsequence problems, Restricted and swap common superstring: a multivariate algorithmic perspective, Improved space-time tradeoffs for approximate full-text indexing with one edit error, Inferring strings from suffix trees and links on a binary alphabet, Frequency-based similarity for parameterized sequences: formal framework, algorithms, and applications, Efficient pattern matching for RNA secondary structures, A space-efficient alphabet-independent Four-Russians' lookup table and a multithreaded Four-Russians' edit distance algorithm, Two fast constructions of compact representations of binary words with given set of periods, Efficient computation of maximal anti-exponent in palindrome-free strings, A prefix array for parameterized strings, Resilient dynamic programming, 2D Lyndon words and applications, Substring range reporting, A hybrid genetic algorithm with solution archive for the discrete \((r|p)\)-centroid problem, Extracting string motif bases for quorum higher than two, A practical semi-external memory method for approximate pattern matching, Faster approximate string matching for short patterns, Fast searching in packed strings, Deciding word neighborhood with universal neighborhood automata, Block-graph width, Adaptive memory programming: local search parallel algorithms for phylogenetic tree construc\-tion, Linear time algorithms for generalizations of the longest common substring problem, The full Steiner tree problem, A structuralist theory of belief revision, Ternary directed acyclic word graphs, Linear-time computation of local periods, Missing pattern discovery, Selected combinatorial problems of computational biology, A survey on tree edit distance and related problems, The intractability of computing the Hamming distance, Space efficient search for maximal repetitions, On suffix extensions in suffix trees, LCS approximation via embedding into locally non-repetitive strings, Efficient algorithms for consensus string problems minimizing both distance sum and radius, Constant-time tree traversal and subtree equality check for grammar-compressed trees, Counting maximal-exponent factors in words, A colored graph approach to perfect phylogeny with persistent characters, Interchange rearrangement: the element-cost model, Maximal and minimal representations of gapped and non-gapped motifs of a string, Suffix tree characterization of maximal motifs in biological sequences, The shortest path problem with forbidden paths, Discovery of stop regions for understanding repeat travel behaviors of moving objects, Space-efficient substring occurrence estimation, A metaheuristic method for vehicle routing problem based on improved ant colony optimization and tabu search, Deposition and extension approach to find longest common subsequence for thousands of long sequences, Top-\(k\) term-proximity in succinct space, An efficient similarity search based on indexing in large DNA databases, Palindromic subsequence automata and longest common palindromic subsequence, Tree edge decomposition with an application to minimum ultrametric tree approximation, On the uniform edge-partition of a tree, The complexity of assigning genotypes to people in a pedigree consistently, An acceleration of FFT-based algorithms for the match-count problem, An improved algorithm for the all-pairs suffix-prefix problem, A linear time algorithm for shortest cyclic cover of strings, Mathematical programming strategies for solving the minimum common string partition problem, Algorithms for subsequence combinatorics, Fast and compact regular expression matching, Construction of component tapes for radial placement machines, Edit distance for a run-length-encoded string and an uncompressed string, Efficient algorithms for finding interleaving relationship between sequences, Learning deterministic context free grammars: the Omphalos competition, Cascading flowlines and layout modules: Practical strategies for machine duplication in facility layouts, Using pattern matching for tiling and packing problems, A hierarchical clustering algorithm for categorical sequence data, Statistical mechanical modeling of a DNA nanobiostructure at the base-pair level, Indexing factors with gaps, Palindromic decompositions with gaps and errors, All-pairs suffix/prefix in optimal time using Aho-Corasick space, Shortest unique palindromic substring queries in semi-dynamic settings, Nonlinear mapping and distance geometry, Comparison methods for branching and axillary flowering sequences, Space-time trade-offs for finding shortest unique substrings and maximal unique matches, Longest common substring with approximately \(k\) mismatches, Extraction of high quality \(k\)-words for alignment-free sequence comparison, Testing the rogue taxa hypothesis for clustering instability, A branch-and-bound framework for unsupervised common event discovery, Linking indexing data structures to de Bruijn graphs: construction and update, An almost quadratic time algorithm for sparse spliced alignment, Dynamic planar range skyline queries in log logarithmic expected time, Note on the greedy parsing optimality for dictionary-based text compression, Irredundant tandem motifs, Speeding up the detection of tandem repeats over the edit distance, Towards optimal packed string matching, Dynamic 3-sided planar range queries with expected doubly-logarithmic time, Dynamic construction of an antidictionary with linear complexity, Revisiting the parameterized complexity of maximum-duo preservation string mapping, Average-case linear-time similar substring searching by the \(q\)-gram distance, Dynamic and internal longest common substring, Computing the Burrows-Wheeler transform of a string and its reverse in parallel, Time-space trade-offs for longest common extensions, Exact mean computation in dynamic time warping spaces, An efficient dynamic programming algorithm for the generalized LCS problem with multiple substring exclusive constraints, Computing a longest common almost-increasing subsequence of two sequences, Prefix-suffix duplication, Computing longest palindromic substring after single-character or block-wise edits, Languages with mismatches, Algorithms for extracting motifs from biological weighted sequences, Linear time algorithm for the longest common repeat problem, Edit distance with move operations, Palindromic trees for a sliding window and its applications, From first principles to the Burrows and Wheeler transform and beyond, via combinatorial optimization, Square network on a word, An all-substrings common subsequence algorithm, Tight approximability results for test set problems in bioinformatics, Nonembeddability theorems via Fourier analysis, Parameter estimation under ambiguity and contamination with the spurious model, Distance measures for biological sequences: some recent approaches, Efficient construction of maximal and minimal representations of motifs of a string, A linear-time algorithm for Hamming distance with shifts, Optimal bounds for computing \({\alpha}\)-gapped repeats, Word assembly through minimal forbidden words, Longest repeats with a block of \(k\) don't cares, Table design in dynamic programming, Succinct non-overlapping indexing, Metrization of the T-alphabet: measuring the distance between multidimensional real discrete sequences, Absent words in a sliding window with applications, Discrete Morse theory for weighted simplicial complexes, A brief history of parameterized matching problems, Approximate pattern matching on elastic-degenerate text, Efficient computation of longest single-arm-gapped palindromes in a string, The alternating BWT: an algorithmic perspective, Longest property-preserved common factor: a new string-processing framework, Counter based suffix tree for DNA pattern repeats, Fully-online suffix tree and directed acyclic word graph construction for multiple texts, On overabundant words and their application to biological sequence analysis, DNA combinatorial messages and epigenomics: the case of chromatin organization and nucleosome occupancy in eukaryotic genomes, Space efficient linear time construction of suffix arrays, Distributed suffix trees, Practical algorithms for transposition-invariant string-matching, Hardness results for the center and median string problems under the weighted and unweighted edit distances, A fully linear-time approximation algorithm for grammar-based compression, Anytime algorithms for the longest common palindromic subsequence problem, Global and local sequence alignment with a bounded number of gaps, A suffix tree or not a suffix tree?, A branch-and-cut algorithm for multiple sequence alignment, A note on the longest common substring with \(k\)-mismatches problem, Longest common substrings with \(k\) mismatches, Fast distance multiplication of unit-Monge matrices, Sparse conformal prediction for dissimilarity data, Anti-unification for unranked terms and hedges, Resequencing a set of strings based on a target string, Space-efficient representation of truncated suffix trees, with applications to Markov order estimation, A space efficient algorithm for the longest common subsequence in \(k\)-length substrings, The longest common subsequence problem for sequences with nested arc annotations., Quasi-median graphs from sets of partitions, Approximate pattern matching and transitive closure logics., Extended suffix array construction using Lyndon factors, Improved upper bounds on all maximal \(\alpha\)-gapped repeats and palindromes, A substring-substring LCS data structure, 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, Space-efficient indexes for forbidden extension queries, Grammar index by induced suffix sorting, The heaviest induced ancestors problem: better data structures and applications, Computing longest common extensions in partial words, On the word fragment length for unambiguous reconstruction of a periodic word from a complete multiset of fragments of fixed length, 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, EERTREE: an efficient data structure for processing palindromes in strings, Searching of gapped repeats and subrepetitions in a word, Efficient codon optimization with motif engineering, Variations of the parameterized longest previous factor, \(p\)-suffix sorting as arithmetic coding, Approximate symbolic pattern matching for protein sequence data, Disjunctive languages related to \(p\)-primitive words, Computing the variance of tour costs over the solution space of the TSP in polynomial time, Unified compression-based acceleration of edit-distance computation, 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., On finding a longest common palindromic subsequence, String matching with inversions and translocations in linear average time (most of the time), Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets, Recent progress on selected topics in database research. -- A report by nine young Chinese researchers working in the United States., Constructing the R* consensus tree of two trees in subcubic time, On the number of gapped repeats with arbitrary gap, Combinatorics of periods in strings., Efficient algorithms for computing the inner edit distance of a regular language via transducers, Hide and seek with repetitions, Fast computation of a longest increasing subsequence and application, A novel statistical measure for sequence comparison on the basis of \(k\)-word counts, Algorithmic complexity of protein identification: Combinatorics of weighted strings, RNA secondary structure comparison: Exact analysis of the Zhang-Shasha tree edit algorithm., An efficient algorithm for LCS problem between two arbitrary sequences, Hardness of approximation for non-overlapping local alignments., Distinguishing string selection problems., 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, Efficient enumeration of maximal induced bicliques, \(xkcd\)-repeats: a new taxonomy of repeats defined by their context diversity, Fifty years of graph matching, network alignment and network comparison, 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, Character-based phylogeny construction and its application to tumor evolution, Flexible indexing of repetitive collections, Combinatorics and algorithms for low-discrepancy roundings of a real sequence, Partial words and the critical factorization theorem, On the hardness of maximum rank aggregation problems, 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, Efficient pattern matching in elastic-degenerate strings, Constructing antidictionaries of long texts in output-sensitive space, Graph traversals, genes and matroids: An efficient case of the travelling salesman problem, The suffix binary search tree and suffix AVL tree, Parallel construction and query of index data structures for pattern matching on square matrices, Approximation algorithms for the shortest total path length spanning tree problem, Repetitive perhaps, but certainly not boring, Solving string problems on graphs using the labeled direct product, Fixed topology alignment with recombination, Reducing space for index implementation., Order-preserving pattern matching indeterminate strings, Finding approximate palindromes in strings, Efficient data reconciliation, An impossibility result for phylogeny reconstruction from \(k\)-mer counts, Bounds for parametric sequence comparison, On maximal repeats in strings, String inference from longest-common-prefix array, Clusters of repetition roots forming prefix chains, Weighted sequence graphs: Boosting iterated dynamic programming using locally suboptimal solutions, Finding similar regions in many sequences, A\textsuperscript{*}-based compilation of relaxed decision diagrams for the longest common subsequence problem, Discovering instances of poetic allusion from anthologies of classical Japanese poems, Tabular parsing and algebraic transformations, Approximate string matching using compressed suffix arrays, A metric index for approximate string matching, Robust variable selection for model-based learning in presence of adulteration, Clusters of repetition roots: single chains, Beam search for the longest common subsequence problem, Scaled and permuted string matching, A fast algorithm for finding the positions of all squares in a run-length encoded string, From Nerode's congruence to suffix automata with mismatches, General suffix automaton construction algorithm and space bounds, Faster subsequence recognition in compressed strings, Construction of Aho Corasick automaton in linear time for integer alphabets, Efficient parameterized string matching, Computing suffix links for suffix trees and arrays, Dynamic programming algorithms for the mosaic longest common subsequence problem, A universal online caching algorithm based on pattern matching, SVM-based detection of distant protein structural relationships using pairwise probabilistic suffix trees, Efficient discovery of unusual patterns in time series, Faster two-dimensional pattern matching with rotations, An efficient algorithm for online square detection, A similarity measure for graphs with low computational complexity, Longest common subsequence problem for unoriented and cyclic strings, An efficient alignment algorithm for masked sequences, Motif discovery by monotone scores, A unifying look at the Apostolico--Giancarlo string-matching algorithm, The consensus string problem for a metric is NP-complete, Compact directed acyclic word graphs for a sliding window, Replacing suffix trees with enhanced suffix arrays, Adaptive text mining: inferring structure from sequences, Parametric multiple sequence alignment and phylogeny construction, Approximation algorithms for Hamming clustering problems, Shift error detection in standardized exams, Compressed parameterized pattern matching, Ensemble clustering by means of clustering embedding in vector spaces, Computing maximal-exponent factors in an overlap-free word, Mining approximate patterns with frequent locally optimal occurrences, Succinct data structures for flexible text retrieval systems, Text indexing with errors, On the approximation of correlation clustering and consensus clustering, Fast profile matching algorithms - A survey, Algorithms for computing variants of the longest common subsequence problem, Computing similarity of run-length encoded strings with affine gap penalty, Converting suffix trees into factor/suffix oracles, On average distortion of embedding metrics into the line, Combinatorial analysis of two basic forms of hidden periodicity in categorial sequences, Comparing bacterial genomes from linear orders of patterns, Periodicity and repetitions in parameterized strings, Finding the longest common subsequence for multiple biological sequences by ant colony optimization, On-line construction of compact suffix vectors and maximal repeats, Efficient on-line repetition detection, An algorithm with linear expected running time for string editing with substitutions and substring reversals, Efficient algorithms for the block edit problems, Lower bounds for optimal alignments of binary sequences, Finite automata based algorithms on subsequences and supersequences of degenerate strings, On the complexity of finding gapped motifs, Dynamic extended suffix arrays, Content-dependent chunking for differential compression, the local maximum approach, Acceleration of the Smith-Waterman algorithm using single and multiple graphics processors, Analysis of a modification of Gusfield's recursive algorithm for reconstructing ultrametric trees, Optimal prefix and suffix queries on texts, Algorithms for clustering clickstream data, A simple attack on some clock-controlled generators, Combinatorics on partial word correlations, An analytical upper bound on the minimum number of recombinations in the history of SNP sequences in populations, Comparing trees via crossing minimization, Finding the longest common nonsuperstring in linear time, Efficient algorithms for the all-pairs suffix-prefix problem and the all-pairs substring-prefix problem, Wee LCP, An efficient polynomial space and polynomial delay algorithm for enumeration of maximal motifs in a sequence, Computational geometric aspects of rhythm, melody, and voice-leading, 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, Compact representations of automata for regular expression matching, 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, Summarizing a set of time series by averaging: from Steiner sequence to compact multiple alignment, On primary and secondary repetitions in words, A faster algorithm for the computation of string convolutions using LZ78 parsing, 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, Constant delay traversal of grammar-compressed graphs with bounded rank, 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, A complete mechanization of correctness of a string-preprocessing algorithm, DISTANCE-BASED PHYLOGENETIC ALGORITHMS: NEW INSIGHTS AND APPLICATIONS, Extending Maximal Perfect Haplotype Blocks to the Realm of Pangenomics, Maintaining traceability links during object-oriented software evolution, Tandem Duplications, Segmental Duplications and Deletions, and Their Applications, DERIVING A FAST SYSTOLIC ALGORITHM FOR THE LONGEST COMMON SUBSEQUENCE PROBLEM, Prefix-Suffix Square Completion, Time-Space Trade-Offs for Longest Common Extensions, EXACT PARALLEL ALIGNMENT OF MEGABASE GENOMIC SEQUENCES WITH TUNABLE WORK DISTRIBUTION, Bethe Ansatz Solution of the Finite Bernoulli Matching Model of Sequence Alignment, A Probabilistic PTAS for Shortest Common Superstring, HYPERCOMPLEX CROSS-CORRELATION OF DNA SEQUENCES, A note of ins-primitive words, Complexity of modification problems for best match graphs, Solving longest common subsequence problems via a transformation to the maximum clique problem, Bit-Parallel Approximate Matching of Circular Strings with k Mismatches, Longest Common Extensions in Trees, Ranked Document Retrieval with Forbidden Pattern, Succinct Non-overlapping Indexing, Reporting Consecutive Substring Occurrences Under Bounded Gap Constraints, Longest Gapped Repeats and Palindromes, Faster repetition-aware compressed suffix trees based on block trees, c-trie++: a dynamic trie tailored for fast prefix searches, Unbordered Pictures: Properties and Construction, Longest $$\alpha $$-Gapped Repeat and Palindrome, On Prefix/Suffix-Square Free Words, A Faster Algorithm for Computing Maximal $$\alpha $$-gapped Repeats in a String, Longest Common Prefix with Mismatches, Constructing Words with High Distinct Square Densities, Hybridizations of Metaheuristics With Branch & Bound Derivates, MINING APPROXIMATE REPEATING PATTERNS FROM SEQUENCE DATA WITH GAP CONSTRAINTS, On the Suffix Automaton with Mismatches, Searching for Gapped Palindromes, Complexity of a Collision-Aware String Partition Problem and Its Relation to Oligo Design for Gene Synthesis, Efficient Algorithms for SNP Haplotype Block Selection Problems, Sequence Alignment Algorithms for Run-Length-Encoded Strings, Unnamed Item, Time-Optimal Top-$k$ Document Retrieval, Most pseudo-copy languages are not context-free, Fast circular dictionary-matching algorithm, Representing prefix and border tables: results on enumeration, The longest common substring problem, Longest Common Subsequence in at Least k Length Order-Isomorphic Substrings, Computing Longest Single-arm-gapped Palindromes in a String, Public key encryption with fuzzy matching, Double string tandem repeats, From Bi-ideals to Periodicity, PROPERTIES AND CONSTRUCTION OF UNIQUE MAXIMAL FACTORIZATION FAMILIES FOR STRINGS, INDEXING GAPPED-FACTORS USING A TREE, REACHABILITY ON SUFFIX TREE GRAPHS, Balance Properties and Distribution of Squares in Circular Words, Efficient Chaining of Seeds in Ordered Trees, Algorithms for Indexing Highly Similar DNA Sequences, Full-Text Indexes for High-Throughput Sequencing, Searching and Indexing Circular Patterns, String-Matching and Alignment Algorithms for Finding Motifs in NGS Data, An Efficient Approach to Merging Paired-End Reads and Incorporation of Uncertainties, IDPM: An Improved Degenerate Pattern Matching Algorithm for Biological Sequences, A PARALLEL ALGORITHM FOR THE CONSTRAINED MULTIPLE SEQUENCE ALIGNMENT PROBLEM DESIGNED FOR GPUs, Palindrome Pattern Matching, Sparse and Truncated Suffix Trees on Variable-Length Codes, Substring Range Reporting, Polynomial-Time Approximation Algorithms for Weighted LCS Problem, Nondeterministic Streaming String Transducers, WEIGHTED AUTOMATA FOR FULL-TEXT INDEXING, A SURVEY ON ALGORITHMIC ASPECTS OF TANDEM REPEATS EVOLUTION, Forty Years of Text Indexing, BALANCE PROPERTIES AND DISTRIBUTION OF SQUARES IN CIRCULAR WORDS, Size and path length of Patricia tries: Dynamical sources context, Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity, Unnamed Item, Parallel Algorithms to Align Multiple Strings in the Context of Web Data Extraction, Construction of a de Bruijn Graph for Assembly from a Truncated Suffix Tree, FINDING ALL APPROXIMATE GAPPED PALINDROMES, Communication-Efficient Private Protocols for Longest Common Subsequence, Random suffix search trees, Online Suffix Tree Construction for Streaming Sequences, Edit Distance Based Encryption and Its Application, Finding Gapped Palindromes Online, LCS Approximation via Embedding into Local Non-repetitive Strings, Fast Searching in Packed Strings, Permuted Longest-Common-Prefix Array, Compressed Multiple Pattern Matching, Dichotomic Selection on Words: A Probabilistic Analysis, Faster queries for longest substring palindrome after block edit, Locally Compressed Suffix Arrays, The conjugacy problem in subgroups of right-angled Artin groups, DC Programming and DCA for Challenging Problems in Bioinformatics and Computational Biology, Making the Error-Controlling Algorithm of Observable Operator Models Constructive, Comparing Degenerate Strings, IN-PLACE UPDATE OF SUFFIX ARRAY WHILE RECODING WORDS, EDIT DISTANCE WITH COMBINATIONS AND SPLITS AND ITS APPLICATIONS IN OCR NAME MATCHING, THE VIRTUAL SUFFIX TREE, Orthogonal Range Searching for Text Indexing, BIT-PARALLEL COMPUTATION OF LOCAL SIMILARITY SCORE MATRICES WITH UNITARY WEIGHTS, FLEXIBLE MUSIC RETRIEVAL IN SUBLINEAR TIME, ONLINE AND DYNAMIC RECOGNITION OF SQUAREFREE STRINGS, Unnamed Item, Periodicity and Repetitions in Parameterized Strings, Computing the Tandem Duplication Distance is NP-Hard, Forbidden Factors and Fragment Assembly, Algorithmic Framework for Approximate Matching Under Bounded Edits with Applications to Sequence Analysis, Finding a Perfect Phylogeny from Mixed Tumor Samples, PAMA: A FAST STRING MATCHING ALGORITHM, Structured Hidden Markov Models: A General Tool for Modeling Agent Behaviors, A FAST TECHNIQUE FOR DERIVING FREQUENT STRUCTURED PATTERNS FROM BIOLOGICAL DATA SETS, On the Structure of Consistent Partitions of Substring Set of a Word, Randomized Shortest-Path Problems: Two Related Models, Pattern Discovery in Colored Strings, Reverse-Safe Text Indexing, Finding top-\(k\) longest palindromes in substrings, Fast detection of specific fragments against a set of sequences, Maximal degenerate palindromes with gaps and mismatches, Parameterized Complexity for Finding a Perfect Phylogeny from Mixed Tumor Samples, Minimum common string partition: on solving large‐scale problem instances, Inferring strings from position heaps in linear time, Finding the cyclic covers of a string, Substring complexities on run-length compressed strings, Computing all-vs-all MEMs in run-length-encoded collections of HiFi reads, On the hardness of computing the edit distance of shallow trees, Data structures for computing unique palindromes in static and non-static strings, A policy-based learning beam search for combinatorial optimization, Computational graph pangenomics: a tutorial on data structures and their applications, An explicit algorithm for normal forms in small overlap monoids, Online algorithms for finding distinct substrings with length and multiple prefix and suffix conditions, Near-optimal quantum algorithms for string problems, Elastic founder graphs improved and enhanced, Unnamed Item, Indefinite Proximity Learning: A Review, Space-Efficient Representations for Glushkov Automata, Palindromic Decompositions with Gaps and Errors, A SCALABLE CLUSTERING METHOD FOR CATEGORICAL SEQUENCE DATA, FITNESS LANDSCAPES AND THE ANDREWS–CURTIS CONJECTURE, A note of prefix n-primitive words, EDIT-DISTANCE OF WEIGHTED AUTOMATA: GENERAL DEFINITIONS AND ALGORITHMS, DICTIONARY LOOK-UP WITHIN SMALL EDIT DISTANCE, Rarity and exponentiality: an extension of Keilson's theorem, with applications, Efficient Computation of 2-Covers of a String., Practical Performance of Space Efficient Data Structures for Longest Common Extensions., A comparison of BWT approaches to string pattern matching, The effect of multiple reference characters on detecting matches in string-searching algorithms, Longest Common Factor After One Edit Operation, Pattern Matching on Elastic-Degenerate Text with Errors, Constructing a Consensus Phylogeny from a Leaf-Removal Distance (Extended Abstract), Fast Label Extraction in the CDAWG, COMBINATORIAL CHARACTERIZATION OF THE LANGUAGE RECOGNIZED BY FACTOR AND SUFFIX ORACLES, Transposition Rearrangement: Linear Algorithm for Length-Cost Model, Analogical Proportions in a Lattice of Sets of Alignments Built on the Common Subwords in a Finite Language, Uncommon suffix tries, Spaces, Trees, and Colors, Unnamed Item, Unnamed Item, Unnamed Item, Approaches to visualization in bioinformatics: From dendrograms to space explorer, Equations enforcing repetitions under permutations, Simple and flexible detection of contiguous repeats using a suffix tree, Beyond evolutionary trees, Indexing Circular Patterns, Sets of Pictures Avoiding Overlaps, Profile of Tries, Unnamed Item, Unnamed Item, Graph Logics with Rational Relations, A sublinear time string prefix square detection algorithm, A characterization of prefix n-power words, Computing the Antiperiod(s) of a String, Finding all maximal perfect haplotype blocks in linear time, Near optimal multiple alignment within a band in polynomial time, Generalizations of suffix arrays to multi-dimensional matrices., Unnamed Item, Small-space LCE data structure with constant-time queries, Unnamed Item, Structural Pattern Matching - Succinctly., Faster Compressed Suffix Trees for Repetitive Collections, Efficient enumeration of non-equivalent squares in partial words with few holes, Locally Maximal Common Factors as a Tool for Efficient Dynamic String Algorithms., Practical lower and upper bounds for the Shortest Linear Superstring, Linear-Time Algorithm for Long LCF with k Mismatches, Longest substring palindrome after edit
