Search

Your search keyword '"Simon J. Puglisi"' showing total 98 results
Start Over Author "Simon J. Puglisi" Publication Type Academic Journals
98 results on '"Simon J. Puglisi"'

1. Suffix sorting via matching statistics

Author

Zsuzsanna Lipták, Francesco Masillo, and Simon J. Puglisi

Subjects
Generalized suffix array, Matching statistics, String collections, Compressed representation, Data structures, Efficient algorithms, Biology (General), QH301-705.5, Genetics, QH426-470
Abstract

Abstract We introduce a new algorithm for constructing the generalized suffix array of a collection of highly similar strings. As a first step, we construct a compressed representation of the matching statistics of the collection with respect to a reference string. We then use this data structure to distribute suffixes into a partial order, and subsequently to speed up suffix comparisons to complete the generalized suffix array. Our experimental evidence with a prototype implementation (a tool we call sacamats) shows that on string collections with highly similar strings we can construct the suffix array in time competitive with or faster than the fastest available methods. Along the way, we describe a heuristic for fast computation of the matching statistics of two strings, which may be of independent interest.

Published
2024
Full Text
View/download PDF

2. Kohdista: an efficient method to index and query possible Rmap alignments

Author

Martin D. Muggli, Simon J. Puglisi, and Christina Boucher

Subjects
Optical mapping, Index based data structures, FM-index, Graph algorithms, Biology (General), QH301-705.5, Genetics, QH426-470
Abstract

Abstract Background Genome-wide optical maps are ordered high-resolution restriction maps that give the position of occurrence of restriction cut sites corresponding to one or more restriction enzymes. These genome-wide optical maps are assembled using an overlap-layout-consensus approach using raw optical map data, which are referred to as Rmaps. Due to the high error-rate of Rmap data, finding the overlap between Rmaps remains challenging. Results We present Kohdista, which is an index-based algorithm for finding pairwise alignments between single molecule maps (Rmaps). The novelty of our approach is the formulation of the alignment problem as automaton path matching, and the application of modern index-based data structures. In particular, we combine the use of the Generalized Compressed Suffix Array (GCSA) index with the wavelet tree in order to build Kohdista. We validate Kohdista on simulated E. coli data, showing the approach successfully finds alignments between Rmaps simulated from overlapping genomic regions. Conclusion we demonstrate Kohdista is the only method that is capable of finding a significant number of high quality pairwise Rmap alignments for large eukaryote organisms in reasonable time.

Published
2019
Full Text
View/download PDF

3. More Time-Space Tradeoffs for Finding a Shortest Unique Substring

Author

Hideo Bannai, Travis Gagie, Gary Hoppenworth, Simon J. Puglisi, and Luís M. S. Russo

Subjects
shortest unique substring, k-mismatch SUS, time-space tradeoff, Karp–Rabin, sketching, suffix trees, Industrial engineering. Management engineering, T55.4-60.8, Electronic computers. Computer science, QA75.5-76.95
Abstract

We extend recent results regarding finding shortest unique substrings (SUSs) to obtain new time-space tradeoffs for this problem and the generalization of finding k-mismatch SUSs. Our new results include the first algorithm for finding a k-mismatch SUS in sublinear space, which we obtain by extending an algorithm by Senanayaka (2019) and combining it with a result on sketching by Gawrychowski and Starikovskaya (2019). We first describe how, given a text T of length n and m words of workspace, with high probability we can find an SUS of length L in O(n(L/m)logL) time using random access to T, or in O(n(L/m)log2(L)loglogσ) time using O((L/m)log2L) sequential passes over T. We then describe how, for constant k, with high probability, we can find a k-mismatch SUS in O(n1+ϵL/m) time using O(nϵL/m) sequential passes over T, again using only m words of workspace. Finally, we also describe a deterministic algorithm that takes O(nτlogσlogn) time to find an SUS using O(n/τ) words of workspace, where τ is a parameter.

Published
2020
Full Text
View/download PDF

12. Block trees.

Author

Djamal Belazzougui, Manuel Cáceres, Travis Gagie, Pawel Gawrychowski, Juha Kärkkäinen, Gonzalo Navarro 0001, Alberto Ordóñez Pereira, Simon J. Puglisi, and Yasuo Tabei

Published
2021
Full Text
View/download PDF

35. Closed factorization.

Author

Golnaz Badkobeh, Hideo Bannai, Keisuke Goto 0001, Tomohiro I, Costas S. Iliopoulos, Shunsuke Inenaga, Simon J. Puglisi, and Shiho Sugimoto

Published
2016
Full Text
View/download PDF

40. Order-preserving matching.

Author

Jinil Kim, Peter Eades, Rudolf Fleischer, Seok-Hee Hong 0001, Costas S. Iliopoulos, Kunsoo Park, Simon J. Puglisi, and Takeshi Tokuyama

Published
2014
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results