On an alternative sequence comparison statistic of Steele

DOI10.23638/DMTCS-22-1-18MaRDI QIDQ3386614zbMATH OpenFDO

Authors Ümit Işlak, Alperen Y. Özdemir

Publication date 5 January 2021

Full work available at URL https://arxiv.org/abs/1803.04052

zbMATH Keywords

central limit theoremlongest common subsequencesrandom wordssimilarity measures

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial probability (60C05) Stochastic processes (60G99)

Abstract: The purpose of this paper is to study a statistic that is used to compare the similarity between two strings, which is first introduced by Michael Steele in 1982. It was proposed as an alternative to the length of the longest common subsequences, for which the variance problem is still open. Our results include moment asymptotics and distributional asymptotics for Steele's statistic and a variation of it in random words and random permutations.

Recommendations

• Statistical considerations underpinning an alignment-free sequence comparison method
• Strong and A-statistical comparisons for sequences
• New powerful statistics for alignment-free sequence comparison under a pattern transfer model
• Sequence comparison. Theory and methods
• Research in Computational Molecular Biology
• Poisson, compound Poisson and process approximations for testing statistical significance in sequence comparisons
• Theoretical Computer Science
• A new combinatorial approach to sequence comparison

Cites work

• Asymptotic results on weakly increasing subsequences in random words
• General methods of sequence comparison
• scientific article; zbMATH DE number 47948 (Why is no real title available?)
• Law of large numbers for increasing subsequences of random permutations
• Long Common Subsequences and the Proximity of Two Random Strings
• Longest common subsequences of two random sequences
• Normal approximation for nonlinear statistics using a concentration inequality approach
• Normal approximations for descents and inversions of permutations of multisets
• Poisson, compound Poisson and process approximations for testing statistical significance in sequence comparisons
• Standard deviation of the longest common subsequence
• The combinatorics of biased riffle shuffles
• The number of increasing subsequences of the random permutation
• The String-to-String Correction Problem

This page was built for publication: On an alternative sequence comparison statistic of Steele

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3386614)