Optimal alignments of longest common subsequences and their path properties
From MaRDI portal
(Redirected from Publication:396006)
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.
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
Cites work
- scientific article; zbMATH DE number 699389 (Why is no real title available?)
- scientific article; zbMATH DE number 5205668 (Why is no real title available?)
- A phase transition for the score in matching random sequences allowing deletions
- An Efron-Stein inequality for nonsymmetric statistics
- Approximate p-values for local sequence alignments.
- Biological Sequence Analysis
- Bounding the expected length of longest common subsequences and forests
- Expected length of the longest common subsequence for large alphabets
- Fluctuations of the longest common subsequence in the asymmetric case of 2- and 3-letter alphabets
- Local alignment of Markov chains
- Longest common subsequences of two random sequences
- Macroscopic non-uniqueness and transversal fluctuation in optimal random sequence alignment
- On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
- On the longest common increasing binary subsequence
- Sequence comparison significance and Poisson approximation
- Sequence comparison. Theory and methods
- Standard deviation of the longest common subsequence
- The rate of convergence of the mean length of the longest common subsequence
- The rate of the convergence of the mean score in random sequence comparison
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
- scientific article; zbMATH DE number 45430 (Why is no real title available?)
- 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)
