3 ms·

the first comment there is reasonable - suffix arrays seem to be preferable anyway (see http://en.wikipedia.org/wiki/Suffix_array http://en.wikipedia.org/wiki/S

the first comment there is reasonable - suffix arrays seem to be preferable anyway (see http://en.wikipedia.org/wiki/Suffix_array http://en.wikipedia.org/wiki/Suffix_array). but i am not a biologist so perhaps i am missing something? (what?) (i am not questioning the wider point about it being nice to have a good suffix tree library; just curious why it's important here). [thanks for the replies]

mbreese 14y ago
I'm fairly certain that it's more efficient to find matches with a certain number of allowed mismatches. I don't think that suffix arrays have as good of performance when you allow for some ambiguity.
kevinwuhoo 14y ago
You're right, generally suffix arrays are more efficient than suffix tries, but biologically there are two reasons why suffix tries are preferred. 1. There are a lot of repeated sequences in biology and many of them are slightly different than each other. For example, we need to insert "difference" and "different" in the structure. The suffix trie would have shared nodes while the suffix array needs an entry for each suffix. 2. Mutations are how evolution takes action. Biologically, in sequences, mutations are just misspellings. If you're looking for a sequence with arbitrary misspellings at position i, a tree structure is easier and faster to traverse. But in reality, most indexing, especially in DNA, uses BWT [1] for indexing. However, there are more complex implementations of suffix arrays that may be suitable [2]. [1]: http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform#BWT_in_bioinformatics http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transfo... [2]: http://www.mi.fu-berlin.de/wiki/pub/ABI/AdvancedAlgorithms11_Indices/script-09-EnhancedSuffixArrays.pdf http://www.mi.fu-berlin.de/wiki/pub/ABI/AdvancedAlgorithms11...
- attractivechaos 14y ago
  Actually just notice that you use "suffix trie". Note that there is trie (which is also called prefix tree) and suffix tree. There is no suffix trie. Suffix array usually uses less memory, but I am not sure in theory it is faster than suffix tree. We can use FM-index and enhanced suffix array (ESA) to simulate trie traversal. You can use ESA to achieve almost everything that you can do with a suffix tree. Trie and suffix tree are natural structures for multiple strings. The typical suffix array is for one string. It is possible to encode multiple strings with suffix array, but that part of theory is not widely used. Also, ESA was introduced in ~2002. It has been well known in CS. Because ESA is in some way a super set of FM-index, you can of course implement those popular mappers with ESA. The key reason that ESA is not widely seen is because it uses much more memory than FM-index. In 2008 when these mappers were greatly needed, no so many machines have 16GB or maybe more needed by ESA.
  - justin66 14y ago
    > Actually just notice that you use "suffix trie". Note that there is trie (which is also called prefix tree) and suffix tree. There is no suffix trie. At the risk of being snotty: someone should tell Robert Sedgwick. He uses the term in his newest book, "An Introduction to the Analysis of Algorithms, Second Edition," which just came out. Sorry if I haven't been fair to your post due to a quick reading but Kevin isn't making the term up.
attractivechaos 14y ago
Suffix array is usually built for ONE string, but in his work, OP probably needs multiple strings, for which trie is a conceptually better representation.

mbreese 14y ago

I'm fairly certain that it's more efficient to find matches with a certain number of allowed mismatches. I don't think that suffix arrays have as good of performance when you allow for some ambiguity.

kevinwuhoo 14y ago

You're right, generally suffix arrays are more efficient than suffix tries, but biologically there are two reasons why suffix tries are preferred. 1. There are a lot of repeated sequences in biology and many of them are slightly different than each other. For example, we need to insert "difference" and "different" in the structure. The suffix trie would have shared nodes while the suffix array needs an entry for each suffix. 2. Mutations are how evolution takes action. Biologically, in sequences, mutations are just misspellings. If you're looking for a sequence with arbitrary misspellings at position i, a tree structure is easier and faster to traverse. But in reality, most indexing, especially in DNA, uses BWT [1] for indexing. However, there are more complex implementations of suffix arrays that may be suitable [2]. [1]: http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transform#BWT_in_bioinformatics http://en.wikipedia.org/wiki/Burrows%E2%80%93Wheeler_transfo... [2]: http://www.mi.fu-berlin.de/wiki/pub/ABI/AdvancedAlgorithms11_Indices/script-09-EnhancedSuffixArrays.pdf http://www.mi.fu-berlin.de/wiki/pub/ABI/AdvancedAlgorithms11...

attractivechaos 14y ago
Actually just notice that you use "suffix trie". Note that there is trie (which is also called prefix tree) and suffix tree. There is no suffix trie. Suffix array usually uses less memory, but I am not sure in theory it is faster than suffix tree. We can use FM-index and enhanced suffix array (ESA) to simulate trie traversal. You can use ESA to achieve almost everything that you can do with a suffix tree. Trie and suffix tree are natural structures for multiple strings. The typical suffix array is for one string. It is possible to encode multiple strings with suffix array, but that part of theory is not widely used. Also, ESA was introduced in ~2002. It has been well known in CS. Because ESA is in some way a super set of FM-index, you can of course implement those popular mappers with ESA. The key reason that ESA is not widely seen is because it uses much more memory than FM-index. In 2008 when these mappers were greatly needed, no so many machines have 16GB or maybe more needed by ESA.
- justin66 14y ago
  > Actually just notice that you use "suffix trie". Note that there is trie (which is also called prefix tree) and suffix tree. There is no suffix trie. At the risk of being snotty: someone should tell Robert Sedgwick. He uses the term in his newest book, "An Introduction to the Analysis of Algorithms, Second Edition," which just came out. Sorry if I haven't been fair to your post due to a quick reading but Kevin isn't making the term up.

attractivechaos 14y ago

Suffix array is usually built for ONE string, but in his work, OP probably needs multiple strings, for which trie is a conceptually better representation.