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
0.9388084411621094
0 references
0.8279130458831787
0 references
0.8204547166824341
0 references
0.813809871673584
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