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 bhighest scoring inversionsinversion alignmentsmitochondrial DNA of Drosophila yakubamouse coding of URF6non-intersecting inversionsoptimal alignments of DNA subsequencesreversed complementssubstitutions, insertions and deletions of nucleotidesURF6 gene

Mathematics Subject Classification ID

Applications of mathematical programming (90C90) Dynamic programming (90C39) Biochemistry, molecular biology (92C40) Protein sequences, DNA sequences (92D20) Computational methods for problems pertaining to biology (92-08)

Related Items (16)

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

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

This page was built for publication: A local algorithm for DNA sequence alignment with inversions