[서평]「Algorithms on Strings, Trees, and Sequences」

By 김동규. 2000

1,821 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/29e2ec607db8760106badf36fc3ed0d8450b1e41

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Artificial error generation for translation-based grammatical error correction (2016, unknown): “2: The Sum of Pairs dynamic programming algorithm for the alignment of three sequences, S1, S2 and S3 (adapted from Gusfield (1997)).”
Tropical Halfspaces (2003, background): “While this is an algorithmic problem of its own [9], there are implementations available that can handle reasonably sized input rather well [1] (including, e.”
Linear-Time Computation of Similarity Measures for Sequential Data (2008, methodology): “Suffix trees are well-known for their ability to enhance run-time performance of string algorithms (Gusfield, 1997).”
A global averaging method for dynamic time warping, with applications to clustering (2011, background): “…for return m[S,T] Algorithm 2. first Require: p ¼ (a, b): couple return a Algorithm 3. second Require: p ¼ (a, b): couple return b Algorithm 4. minVal Require: v1, v2, v3: couple if firstðv1Þrminðfirstðv2Þ,firstðv3ÞÞ then return v1 else if firstðv2Þr firstðv3Þ then return v2 else return v3 end if”
Biclustering algorithms for biological data analysis: a survey (2004, unknown): “The suffix tree [12] is built by assuming a given, arbitrary, lexicographic order on the columns.”
Efficient large-scale sequence comparison by locality-sensitive hashing (2001, background): “…algorithms can efficiently detect ungapped alignments containing few substitutions (substantially fewer than d/ log 4 d for alignments of length d; Gusfield, 1997, Section 12.3); however, for the range of ungapped alignment lengths that are useful as seeds, the algorithms' performance degrades…”
Honeycomb (2004, methodology): “Using suffix trees, the longest common substring of two strings is straightforward to find in linear time [7].”
Kernel Methods in Computer Vision (2009, unknown): “…densities p, p′: k(p, p′) = exp(−JS(p, p′)), where JS(p, p′) = 1 2 ∫ R p(x) log p(x)1 2(p(x) + p′(x)) +p′(x) log p ′(x) 1 2(p(x) + p′(x)) is the Jensen-Shannon divergence [Hein and Bousquet, 2005], • for strings s, s′: k(s, s′) = exp(−D(s, s′)), where D(s, s′) is the edit distance [Gusfield, 1997].”
Clustered Sequence Representation for Fast Homology Search (2007, unknown): “Malde et al. (2003) and Gracy and Argos (1998) investigated the use of sufﬁx structures such as sufﬁx trees (Gusﬁeld, 1997) and sufﬁx arrays (Manber and Myers, 1993) to identify groupings of similar sequences in linear time.”
FAMSA: Fast and accurate multiple sequence alignment of huge protein families (2016, methodology): “12 Thanks to the internal properties of the DP matrix, the calculation can be made using the bit-parallel approach, in which w cells are computed at a time ( w is a computer word size equal to 64 in modern architectures).”