Pattern Discovery: Methods and Software
Broňa Brejová, Tomáš Vinař, Ming Li · Humana Press eBooks · 2003
3 Algorithms for Pattern Discovery 6 3.1 Exhaustive search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.1.1 Enumerating all patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 3.1.2 Exhaustive search on graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 3.2 Creating long patterns from short patterns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2.1 TEIRESIAS algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 3.2.2 Improvement of running time . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3 Iterative heuristic methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3.1 Gibbs sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3.3.2 Other iterative methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12 3.3.3 From iteration to PTAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.4 Machine learning methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.4.1 Expectation maximization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 3.4.2 Hidden Markov models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 3.4.3 Enhancing HMM models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3.5 Methods using additional information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.5.1 Identifying motifs in aligned sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.5.2 Global properties of a sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 3.5.3 Using phylogenetic tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.5.4 Use of secondary/tertiary structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 3.6 Finding homologies between two sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19