Optimal alignments of longest common subsequences and their path properties
From MaRDI portal
Publication:396006
DOI10.3150/13-BEJ522zbMATH Open1312.60004arXiv1407.1233OpenAlexW2003308075MaRDI QIDQ396006FDOQ396006
Authors: J. Lember, Anna Vollmer, Heinrich Matzinger 
Publication date: 8 August 2014
Published in: Bernoulli (Search for Journal in Brave)
Abstract: We investigate the behavior of optimal alignment paths for homologous (related) and independent random sequences. An alignment between two finite sequences is optimal if it corresponds to the longest common subsequence (LCS). We prove the existence of lowest and highest optimal alignments and study their differences. High differences between the extremal alignments imply the high variety of all optimal alignments. We present several simulations indicating that the homologous (having the same common ancestor) sequences have typically the distance between the extremal alignments of much smaller size than independent sequences. In particular, the simulations suggest that for the homologous sequences, the growth of the distance between the extremal alignments is logarithmical. The main theoretical results of the paper prove that (under some assumptions) this is the case, indeed. The paper suggests that the properties of the optimal alignment paths characterize the relatedness of the sequences.
Full work available at URL: https://arxiv.org/abs/1407.1233
Recommendations
- Closeness to the diagonal for longest common subsequences in random words
- Microscopic path structure of optimally aligned random sequences
- Letter change bias and local uniqueness in optimal sequence alignments
- scientific article; zbMATH DE number 45430
- On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
Large deviations (60F10) Inequalities; stochastic orderings (60E15) Combinatorial probability (60C05)
Cites Work
- Biological Sequence Analysis
- Expected length of the longest common subsequence for large alphabets
- An Efron-Stein inequality for nonsymmetric statistics
- Local alignment of Markov chains
- 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
- Standard deviation of the longest common subsequence
- Fluctuations of the longest common subsequence in the asymmetric case of 2- and 3-letter alphabets
- Longest common subsequences of two random sequences
- Title not available (Why is that?)
- The rate of the convergence of the mean score in random sequence comparison
- Title not available (Why is that?)
- On the longest common increasing binary subsequence
- Sequence comparison significance and Poisson approximation
- Bounding the expected length of longest common subsequences and forests
- Approximate \(p\)-values for local sequence alignments.
- On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
- Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment
- Sequence comparison. Theory and methods
Cited In (15)
- Standard deviation of the longest common subsequence
- Sparse LCS Common Substring Alignment
- Letter change bias and local uniqueness in optimal sequence alignments
- Closeness to the diagonal for longest common subsequences in random words
- Sparse LCS common substring alignment
- On computing all suboptimal alignments
- A path selection approach to global pairwise sequence alignment using integer linear optimization†
- Path reversal, islands, and the gapped alignment of random sequences
- On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
- Title not available (Why is that?)
- On the variance of the optimal alignments score for binary random words and an asymmetric scoring function
- Optimality regions and fluctuations for Bernoulli last passage models
- Microscopic path structure of optimally aligned random sequences
- Thermodynamical approach to the longest common subsequence problem
- Generalized sequence alignment and duality
This page was built for publication: Optimal alignments of longest common subsequences and their path properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q396006)
