Name
Abstract | ||
|---|---|---|
The Longest Common Factor (LCF) of a set of strings is a well studied problem having a wide range of applications in Bioinformatics: from microarrays to DNA sequences analysis. This problem has been solved by Hui (2000) who uses a famous constant-time solution to the Lowest Common Ancestor (LCA) problem in trees coupled with use of suffix trees. A data structure for the LCA problem, although linear in space and construction time, introduces a multiplicative constant in both space and time that reduces the range of applications in many biological applications. In this article we present a new method for solving the LCF problem using the suffix tree structure with an auxiliary array that take space O(n). Our algorithm works in time O(n log a), where n is the total input size and a is the size of the alphabet. We also consider a different version of our algorithm that applies to DAWGs. In this case, we prove that the algorithm works in both time and space proportional to data DAWG's size. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1007/978-0-387-09680-3_10 | International Federation for Information Processing |
Keywords | Field | DocType |
lowest common ancestor,dna sequence analysis,data structure | Data structure,Discrete mathematics,Combinatorics,Lowest common ancestor,Multiplicative function,Suffix,Spacetime,Suffix tree,Generalized suffix tree,Mathematics,Longest common substring problem | Conference |
Volume | ISSN | Citations |
273 | 1571-5736 | 1 |
PageRank | References | Authors |
0.36 | 12 | 4 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Maxime Crochemore | 1 | 2655 | 281.75 |
| A. Gabriele | 2 | 24 | 3.37 |
| Filippo Mignosi | 3 | 569 | 99.71 |
| Mauriana Pesaresi | 4 | 1 | 0.36 |