A local algorithm for DNA sequence alignment with inversions

DOI10.1007/BF02459633zbMath0745.92020WikidataQ42611189 ScholiaQ42611189MaRDI QIDQ1191622

Michael S. Waterman, Michael Schöniger

Publication date: 27 September 1992

Published in: Bulletin of Mathematical Biology (Search for Journal in Brave)

zbMATH Keywords

cytochrome b; highest scoring inversions; inversion alignments; mitochondrial DNA of Drosophila yakuba; mouse coding of URF6; non-intersecting inversions; optimal alignments of DNA subsequences; reversed complements; substitutions, insertions and deletions of nucleotides; URF6 gene

Mathematics Subject Classification ID

90C90: Applications of mathematical programming

90C39: Dynamic programming

92C40: Biochemistry, molecular biology

92D20: Protein sequences, DNA sequences

92-08: Computational methods for problems pertaining to biology

Related Items

A sparse dynamic programming algorithm for alignment with non-overlapping inversions, Category theory for genetics I: mutations and sequence alignments, On the Simon's congruence neighborhood of languages, Rich words in the block reversal of a word, Efficient string-matching allowing for non-overlapping inversions, Non-overlapping inversion on strings and languages, An efficient algorithm to detect common ancestor genes for non-overlapping inversion and applications, Alignments with non-overlapping moves, inversions and tandem duplications in \(O(n^{4})\) time, Walking tree heuristics for comparative genomic alignments., A space-efficient algorithm for sequence alignment with inversions and reversals, Exact and approximation algorithms for sorting by reversals, with application to genome rearrangement, Pseudo-inversion: closure properties and decidability, Block reversal on finite words, Alignment with non-overlapping inversions and translocations on two strings, Duplications and Pseudo-Duplications, Efficient Matching of Biological Sequences Allowing for Non-overlapping Inversions

Cites Work

• The Erdős-Rényi law in distribution, for coin tossing and sequence matching
• General methods of sequence comparison
• Two moments suffice for Poisson approximations: The Chen-Stein method
• Poisson, compound Poisson and process approximations for testing statistical significance in sequence comparisons
• Some biological sequence metrics
• Methods for assessing the statistical significance of molecular sequence features by using general scoring schemes.
• Stochastic scrabble: large deviations for sequences with scores