No label defined (Q4731047)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 4116363
Language Label Description Also known as
default for all languages
No label defined
    English
    No label defined
    scientific article; zbMATH DE number 4116363

      Statements

      1989
      0 references
      DNA
      0 references
      string-matching
      0 references
      alignment algorithm
      0 references
      consensus subsequences
      0 references
      consensus palindromes
      0 references
      long consensus patterns
      0 references
      [For the entire collection see Zbl 0674.00024.] Several sequences of common function may contain a common functional subsequence which has been conserved, although perhaps not exactly. This paper gives a practical alignment algorithm for finding such consensus subsequences. The algorithm slides a window along the sequences and finds similar k letter words within the window in each sequence. The algorithm time is (loosely speaking) O(rn), where r is the number of sequences and n is the length of the sequences, rather than the usual \(O(n^ r)\) of dynamic programming algorithms. The practical application of the algorithm to finding consensus palindromes, long consensus patterns, and consensus in one sequence, and the use of large deviations theory to find the statistical significance of results is discussed.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references