Using suffix tree to discover complex repetitive patterns in DNA sequences

D He - 2006 International Conference of the IEEE Engineering …, 2006 - ieeexplore.ieee.org
2006 International Conference of the IEEE Engineering in Medicine …, 2006ieeexplore.ieee.org
The discovery of repetitive patterns is a fundamental problem in bioinformatics. It remains a
challenging open problem because most of the existing methods, such as using annotated
repeat database and extracting pairs of maximum repeated regions, can not give a correct
definition incorporating both the length and frequency factors of the repetitive patterns. There
is an algorithm considering both the pattern length and frequency. However, it could only
find the simple" elementary" repeats and is not able to reveal the complex structure of the …
The discovery of repetitive patterns is a fundamental problem in bioinformatics. It remains a challenging open problem because most of the existing methods, such as using annotated repeat database and extracting pairs of maximum repeated regions, can not give a correct definition incorporating both the length and frequency factors of the repetitive patterns. There is an algorithm considering both the pattern length and frequency. However, it could only find the simple "elementary" repeats and is not able to reveal the complex structure of the repetitive patterns. Furthermore, its time complexity O(n 2 f), where n is the length of the sequence, f is the minimum frequency requirement, could be still too high for long DNA sequences. In this paper, we propose a novel algorithm using suffix tree to reveal the complex structure of the repetitive patterns in DNA sequences. We show that our algorithm achieves an O(n 2 f 2 ) time complexity
ieeexplore.ieee.org
以上显示的是最相近的搜索结果。 查看全部搜索结果