Abstract | ||
---|---|---|
Variable order Markov chains (VOMCs) are a flexible class of models that extend the well-known Markov chains. They have been applied to a variety of problems in computational biology, e.g. protein family classification. A linear time and space construction algorithm has been published in 2000 by Apostolico and Bejerano. However, neither a report of the actual running time nor an implementation of it have been published since. In this paper we use the lazy suffix tree and the enhanced suffix array to improve upon the algorithm of Apostolico and Bejerano. We introduce a new software which is orders of magnitude faster than current tools for building VOMCs, and is suitable for large scale sequence analysis. |
Year | DOI | Venue |
---|---|---|
2008 | 10.1007/978-3-540-87361-7_26 | WABI |
Keywords | Field | DocType |
variable order markov chain,flexible class,chain construction,lazy suffix tree,current tool,enhanced suffix array,adaptive variable order markov,well-known markov chain,linear time,computational biology,space construction algorithm,large scale sequence analysis,markov chain,sequence analysis,computer science,g protein | Computer science,Theoretical computer science,Software,Generalized suffix tree,Suffix tree,Time complexity,Combinatorics,Markov chain,Algorithm,Suffix array,Variable-order Markov model,Bioinformatics,Compressed suffix array | Conference |
Volume | ISSN | Citations |
5251 | 0302-9743 | 9 |
PageRank | References | Authors |
0.49 | 24 | 6 |
Name | Order | Citations | PageRank |
---|---|---|---|
Marcel H Schulz | 1 | 240 | 24.03 |
David Weese | 2 | 252 | 17.79 |
Tobias Rausch | 3 | 262 | 18.00 |
Andreas Döring | 4 | 195 | 19.38 |
Knut Reinert | 5 | 1020 | 105.87 |
Martin Vingron | 6 | 1754 | 298.16 |