摘要: Given an input sequence of data, a "rigid" pattern is repeating sequence, possibly interspersed with "dont care" characters. In practice, the patterns or motifs interest are ones that also allow variable number gaps (or characters): we call these flexible motifs. The rigid could potentially be exponential in size and case where real numbers, there uncountably infinite (assuming two numbers equal if they within some δ > 0 each other). It has been shown earlier by suitably defining notion maximality redundancy, exists only linear no more than 3n) irredundant polynomial time algorithm to detect Here present uniform framework encompasses both generalizations sets show somewhat surprising result still have bound. However, them higher complexity
springer.com
sci-hub.st 参考文章(35)
Laxmi P. Parida, Bud Mishra, Algorithmic techniques in computational genomics New York University. ,(1998)
Aris Floratos, Isidore Rigoutsos, Laxmi Parida, MUSCA: An Algorithm for Constrained Alignment of Multiple Data Sequences. Genome Informatics. ,vol. 9, pp. 112- 119 ,(1998) , 10.11234/GI1990.9.112
Laxmi Parida, Aris Floratos, Isidore Rigoutsos, An Approximation Algorithm for Alignment of Multiple Sequences using Motif Discovery Journal of Combinatorial Optimization. ,vol. 3, pp. 247- 275 ,(1999) , 10.1023/A:1009841927822
Gautam Das, Dimitrios Gunopulos, Heikki Mannila, Finding Similar Time Series european conference on principles of data mining and knowledge discovery. pp. 88- 100 ,(1997) , 10.1007/3-540-63223-9_109
Heikki Mannila, A. Inkeri Verkamo, Ramakrishnan Srikant, Hannu Toivonen, Rakesh Agrawal, Fast discovery of association rules knowledge discovery and data mining. pp. 307- 328 ,(1996)
Marie -France Sagot, Alain Viari, A Double Combinatorial Approach to Discovering Patterns in Biological Sequences combinatorial pattern matching. pp. 186- 208 ,(1996) , 10.1007/3-540-61258-0_15
Comparative Analysis of Multiple Protein-Sequence Alignment Methods Molecular Biology and Evolution. ,vol. 11, pp. 571- 592 ,(1994) , 10.1093/OXFORDJOURNALS.MOLBEV.A040138
M WATERMAN, Parametric and ensemble sequence alignment algorithms Bulletin of Mathematical Biology. ,vol. 56, pp. 743- 767 ,(1994) , 10.1016/S0092-8240(05)80311-8
Humberto Carrillo, David Lipman, The multiple sequence alignment problem in biology Siam Journal on Applied Mathematics. ,vol. 48, pp. 1073- 1082 ,(1988) , 10.1137/0148063
Z. Zhang, B. He, W. Miller, Local multiple alignment via subgraph enumeration Discrete Applied Mathematics. ,vol. 71, pp. 337- 365 ,(1996) , 10.1016/S0166-218X(96)00072-8