No label defined (Q4731046)
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 4116362
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 4116362 |
Statements
1989
0 references
string-matching
0 references
DNA
0 references
Combinatorics
0 references
Dynamic programming algorithms
0 references
Line geometries
0 references
neighborhoods of consensus words
0 references
multiple sequence alignments
0 references
Hashing techniques
0 references
subsequence similarities
0 references
Subadditive processes
0 references
Erdős Renyi laws
0 references
distribution of longest matches
0 references
phase transition
0 references
0.8338862657546997
0 references
0.8244578838348389
0 references
0.8184539079666138
0 references
[For the entire collection see Zbl 0674.00024.] This paper gives a breath takingly rapid survey of mathematical methods in sequence alignment. Combinatorics give the number of alignments between two sequences. Dynamic programming algorithms produce optimal or near optimal alignment of sequences and subsequences. Line geometries and neighborhoods of consensus words give multiple sequence alignments. Hashing techniques search databases for subsequence similarities. Subadditive processes and probability theory give Erdős Renyi laws for the distribution of longest matches between sequences. The distribution of these subsequence match scores displays a phase transition, going from linear to logarithmic as a function of sequence length when gap penalties range from zero to infinite. Some open problems remain in the precise mathematical description of this transition.
0 references