|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--org.biojava.bio.symbol.SuffixTree
Suffix tree implementation. The interface is a bit strange, as it needed to be as space-efficient as possible. More work could be done on the space issue.
A suffix tree is an efficient method for encoding the frequencies
of motifs in a sequence. They are sometimes used to quickly screen
for similar sequences. For instance, all motifs of length up to
2 in the sequence AAGT
could be encoded as:
root(4) | A(2)--------G(1)-----T(1) | | A(1)--G(1) T(1)
A possible method of comparing SuffixTrees is provided as a kernel
function as org.biojava.stats.svm.tools.SuffixTreeKernel
.
Inner Class Summary | |
static class |
SuffixTree.SuffixNode
A node in the suffix tree. |
Constructor Summary | |
SuffixTree(FiniteAlphabet alphabet)
Construct a new SuffixTree to contain motifs over the specified alphabet. |
Method Summary | |
void |
addSymbols(SymbolList rList,
int window)
Add a count for all motifs with length of up to window
to this tree. |
int |
frequency(int length)
Return the number of motifs of a given length encoded in this SuffixTree. |
FiniteAlphabet |
getAlphabet()
Return the Alphabet containing all Symbols which might be found in this SuffixTree. |
SuffixTree.SuffixNode |
getChild(SuffixTree.SuffixNode node,
int i)
Get the n'th child of a node. |
SuffixTree.SuffixNode |
getChild(SuffixTree.SuffixNode node,
Symbol r)
Get a child of a SuffixTree.SuffixNode, constructing a new one if need be. |
SuffixTree.SuffixNode |
getRoot()
Return the node object which is the root of this suffix tree. |
protected void |
incCounts(int i,
int c)
|
int |
indexForSymbol(Symbol r)
Return an internal index number corresponding to the given Symbol. |
int |
maxLength()
Return the length of the longest motif represented in this SuffixTree |
Symbol |
symbolForIndex(int i)
Return the Symbol corresponding to a specified index number. |
Methods inherited from class java.lang.Object |
clone,
equals,
finalize,
getClass,
hashCode,
notify,
notifyAll,
toString,
wait,
wait,
wait |
Constructor Detail |
public SuffixTree(FiniteAlphabet alphabet)
alphabet
- The alphabet of this SuffixTree (must be
finite).Method Detail |
public FiniteAlphabet getAlphabet()
public SuffixTree.SuffixNode getRoot()
public SuffixTree.SuffixNode getChild(SuffixTree.SuffixNode node, Symbol r)
public SuffixTree.SuffixNode getChild(SuffixTree.SuffixNode node, int i)
public void addSymbols(SymbolList rList, int window)
window
to this tree.rList
- a SymbolList whose motifs should be added to the
tree.window
- The maximum motif length to count.protected void incCounts(int i, int c)
public int maxLength()
public int frequency(int length)
public Symbol symbolForIndex(int i)
public int indexForSymbol(Symbol r)
|
|||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | ||||||||
SUMMARY: INNER | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |