Optimal alignments of longest common subsequences and their path properties

DOI10.3150/13-BEJ522zbMath1312.60004arXiv1407.1233MaRDI QIDQ396006

Jüri Lember, Anna Vollmer, Heinrich III Matzinger

Publication date: 8 August 2014

Published in: Bernoulli (Search for Journal in Brave)

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

zbMATH Keywords

homologous sequences; longest common subsequence; optimal alignments

Mathematics Subject Classification ID

60E15: Inequalities; stochastic orderings

60C05: Combinatorial probability

60F10: Large deviations

Related Items

Optimality regions and fluctuations for Bernoulli last passage models, Standard deviation of the longest common subsequence

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The rate of the convergence of the mean score in random sequence comparison
• On the longest common increasing binary subsequence
• Local alignment of Markov chains
• Sequence comparison. Theory and methods
• An Efron-Stein inequality for nonsymmetric statistics
• Bounding the expected length of longest common subsequences and forests
• A phase transition for the score in matching random sequences allowing deletions
• The rate of convergence of the mean length of the longest common subsequence
• Sequence comparison significance and Poisson approximation
• Approximate \(p\)-values for local sequence alignments.
• Standard deviation of the longest common subsequence
• On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
• Expected length of the longest common subsequence for large alphabets
• Longest common subsequences of two random sequences
• Biological Sequence Analysis
• Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment