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
- 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
- scientific article; zbMATH DE number 699389 (Why is no real title available?)
- scientific article; zbMATH DE number 5205668 (Why is no real title available?)
- 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
(16)- Sparse LCS common substring alignment
- Generalized sequence alignment and duality
- On computing all suboptimal alignments
- Optimality regions and fluctuations for Bernoulli last passage models
- Standard deviation of the longest common subsequence
- On suboptimal LCS-alignments for independent Bernoulli sequences with asymmetric distributions
- Microscopic path structure of optimally aligned random sequences
- Letter change bias and local uniqueness in optimal sequence alignments
- Closeness to the diagonal for longest common subsequences in random words
- On the variance of the optimal alignments score for binary random words and an asymmetric scoring function
- Sparse LCS Common Substring Alignment
- scientific article; zbMATH DE number 45430 (Why is no real title available?)
- Path reversal, islands, and the gapped alignment of random sequences
- A path selection approach to global pairwise sequence alignment using integer linear optimization†
- Title not available (Why is no real title available?)
- Thermodynamical approach to the longest common subsequence problem
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)
