检索结果-内蒙古大学图书馆

Generalizations of suffix arrays to multi-dimensional matrices

THEORETICAL COMPUTER SCIENCE 2003年第1-3期302卷 401-416页

作者： Kim, DK Kim, YA Park, K Seoul Natl Univ Sch Engn & Comp Sci Seoul 151742 South Korea Univ Maryland Dept Comp Sci College Pk MD 20742 USA Pusan Natl Univ Sch Elect & Comp Engn Pusan 609735 South Korea

We propose multi-dimensional index data structures that generalize suffix arrays to square matrices and cubic matrices. Giancarlo proposed a two-dimensional index data structure, the Lsuffix tree, that generalizes suffix trees to square matrices. However, the construction algorithm for Lsuffix trees maintains complicated data structures and uses a large amount of space. We present simple construction algorithms for multi-dimensional suffix arrays by applying a new partitioning technique to lexicographic sorting. Our contributions are the first efficient algorithms for constructing two-dimensional and three-dimensional suffix arrays directly. (C) 2002 Published by Elsevier Science B.V.

关键词： index data structure suffix array multi-dimensional matrices pattern retrieval

来源：评论

学校读者我要写书评

暂无评论

Large-Scale Pattern Search Using Reduced-Space On-Disk suffix arrays

引用

IEEE TRANSACTIONS ON KNOWLEDGE AND DATA ENGINEERING 2014年第8期26卷 1918-1931页

作者： Gog, Simon Moffat, Alistair Culpepper, J. Shane Turpin, Andrew Wirth, Anthony Univ Melbourne Dept Comp & Informat Syst Melbourne Vic 3010 Australia RMIT Univ Sch Comp Sci & Informat Technol Melbourne Vic 3001 Australia

The suffix array is an efficient data structure for in-memory pattern search. suffix arrays can also be used for external-memory pattern search, via two-level structures that use an internal index to identify the correct block of suffix pointers. In this paper, we describe a new two-level suffix array-based index structure that requires significantly less disk space than previous approaches. Key to the saving is the use of disk blocks that are based on prefixes rather than the more usual uniform-sampling approach, allowing reductions between blocks and subparts of other blocks. We also describe a new in-memory structure-the condensed BWT-and show that it allows common patterns to be resolved without access to the text. Experiments using 64 GB of English web text on a computer with 4 GB of main memory demonstrate the speed and versatility of the new approach. For this data, the index is around one-third the size of previous two-level mechanisms;and the memory footprint of as little as 1% of the text size means that queries can be processed more quickly than is possible with a compact FM-INDEX.

关键词： String search pattern matching suffix array Burrows-Wheeler transform succinct data structure disk-based algorithm experimental evaluation

来源：评论

学校读者我要写书评

暂无评论

New text indexing functionalities of the compressed suffix arrays

引用

JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC 2003年第2期48卷 294-313页

作者： Sadakane, K Kyushu Univ Dept Comp Sci & Commun Engn Fukuoka 8128581 Japan

New text indexing functionalities of the compressed suffix arrays are proposed. The compressed suffix array proposed by Grossi and Vitter is a space-efficient data structure for text indexing. It occupies only O (n) bits for a text of length n;however it also uses the text itself that occupies n log(2) \A\ bits for the alphabet A. In this paper we modify the data structure so that pattern matching can be done without any access to the text. In addition to the original functions of the compressed suffix array, we add new operations search, decompress and inverse to the compressed suffix arrays. We show that the new index can find occ occurrences of any substring P of the text in O (\P\ log n + occ log(epsilon) n) time for any fixed 1 greater than or equal to epsilon > 0 without access to the text. The index also can decompress a part of the text of length m in O (m + log(epsilon) n) time. For a text of length n on an alphabet A such that \A\ = polylog(n), our new index occupies only O (nH(0) + n log log \A\) bits where H-0 less than or equal to log \A\ is the order-0 entropy of the text. Especially for epsilon = 1 the size is n H-0 + O (n log log \A\) bits. Therefore the index will be smaller than the text, which means we can perform fast queries from compressed texts. (C) 2003 Elsevier Inc. All rights reserved.

关键词： text database suffix array compression

来源：评论

学校读者我要写书评

暂无评论

Repeated patterns detection in big data using classification and parallelism on LERP Reduced suffix arrays

引用

APPLIED INTELLIGENCE 2016年第3期45卷 567-597页

作者： Xylogiannopoulos, Konstantinos F. Karampelas, Panagiotis Alhajj, Reda Univ Calgary Dept Comp Sci Calgary AB Canada Hellen Air Force Acad Dept Informat & Comp Dekelia Air Base Acharnes Greece

suffix array is a powerful data structure, used mainly for pattern detection in strings. The main disadvantage of a full suffix array is its quadratic O(n (2) ) space capacity when the actual suffixes are needed. In our previous work [39], we introduced the innovative All Repeated Patterns Detection (ARPaD) algorithm and the Moving Longest Expected Repeated Pattern (MLERP) process. The former detects all repeated patterns in a string using a partition of the full suffix array and the latter is capable of analyzing large strings regardless of their size. Furthermore, the notion of Longest Expected Repeated Pattern (LERP), also introduced by the authors in a previous work, significantly reduces to linear O ( n ) the space capacity needed for the full suffix array. However, so far the LERP value has to be specified in ad hoc manner based on experimental or empirical values. In order to overcome this problem, the Probabilistic Existence of LERP theorem has been proven in this paper and, furthermore, a formula for an accurate upper bound estimation of the LERP value has been introduced using only the length of the string and the size of the alphabet used in constructing the string. The importance of this method is the optimum upper bounding of the LERP value without any previous preprocess or knowledge of string characteristics. Moreover, the new data structure LERP Reduced suffix array is defined;it is a variation of the suffix array, and has the advantage of permitting the classification and parallelism to be implemented directly on the data structure. All other alternative methodologies deal with the very common problem of fitting any kind of data structure in a computer memory or disk in order to apply different time efficient methods for pattern detection. The current advanced and elegant proposed methodology allows us to alter the above-mentioned problem such that smaller classes of the problem can be distributed on different systems and then apply current, state-o

关键词： suffix array LERP-reduced suffix array String Sequence Longest expected reapeated pattern Moving LERP Normal number Random string Pattern detection Classification Parallelism

来源：评论

学校读者我要写书评

暂无评论

On arithmetically progressed suffix arrays and related Burrows-Wheeler transforms

引用

DISCRETE APPLIED MATHEMATICS 2024年 355卷 180-199页

作者： Daykin, Jacqueline W. Koppl, Dominik Kubel, David Stober, Florian Aberystwyth Univ Dept Comp Sci Aberystwyth Wales Normandie Univ Univ Rouen Normandie Univ Le Havre Normandie INSA Rouen NormandieLITIS F-76000 Rouen France Stellenbosch Univ Dept Informat Sci Stellenbosch South Africa Univ Yamanashi Dept Comp Sci & Engn Kofu Japan Univ Bonn Inst Comp Sci Bonn Germany Univ Stuttgart Inst Formal Methods Comp Sci FMI Stuttgart Germany

We characterize those strings whose suffix arrays are based on arithmetic progressions, in particular, arithmetically progressed permutations where all pairs of successive entries of the permutation have the same difference modulo the respective string length. We show that an arithmetically progressed permutation P coincides with the suffix array of a unary, binary, or ternary string. We further analyze the conditions of a given P under which we can find a uniquely defined string over either a binary or ternary alphabet having P as its suffix array. For the binary case, we show its connection to lower Christoffel words, balanced words, and Fibonacci words. In addition to solving the arithmetically progressed suffix array problem, we give the shape of the Burrows- Wheeler transform of those strings solving this problem. These results give rise to numerous future research directions. (c) 2024 The Authors. Published by Elsevier B.V. This is an open access article under the CC BY license (http://***/licenses/by/4.0/).

关键词： Arithmetic progression Burrows-Wheeler transform Christoffel words suffix array String combinatorics

来源：评论

学校读者我要写书评

暂无评论

Efficient repeat finding in sets of strings via suffix arrays

引用

DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE 2013年第2期15卷 59-70页

作者： Barenbaum, Pablo Becher, Veronica Deymonnaz, Alejandro Halsband, Melisa Ariel Heiber, Pablo Univ Buenos Aires Fac Ciencias Exactas & Nat Dept Computac RA-1053 Buenos Aires DF Argentina CONICET Argentina Buenos Aires DF Argentina

We consider two repeat finding problems relative to sets of strings: (a) Find the largest substrings that occur in every string of a given set;(b) Find the maximal repeats in a given string that occur in no string of a given set. Our solutions are based on the suffix array construction, requiring O (m) memory, where m is the length of the longest input string, and O (n log m) time, where n is the the whole input size (the sum of the length of each string in the input). The most expensive part of our algorithms is the computation of several suffix arrays. We give an implementation and experimental results that evidence the efficiency of our algorithms in practice, even for very large inputs.

关键词： stringology repeats suffix array longest maximal substring

来源：评论

学校读者我要写书评

暂无评论

GeDi: applying suffix arrays to increase the repertoire of detectable SNVs in tumour genomes

引用

BMC BIOINFORMATICS 2020年第1期21卷 45-45页

作者： Coleman, Izaak Corleone, Giacomo Arram, James Ng, Ho-Cheung Magnani, Luca Luk, Wayne Imperial Coll London Dept Comp London SW7 2AZ England Columbia Univ Syst Biol PhD Program New York NY USA Imperial Coll Hammersmith Dept Surg & Canc London W12 England

Background Current popular variant calling pipelines rely on the mapping coordinates of each input read to a reference genome in order to detect variants. Since reads deriving from variant loci that diverge in sequence substantially from the reference are often assigned incorrect mapping coordinates, variant calling pipelines that rely on mapping coordinates can exhibit reduced sensitivity. Results In this work we present GeDi, a suffix array-based somatic single nucleotide variant (SNV) calling algorithm that does not rely on read mapping coordinates to detect SNVs and is therefore capable of reference-free and mapping-free SNV detection. GeDi executes with practical runtime and memory resource requirements, is capable of SNV detection at very low allele frequency (<1%), and detects SNVs with high sensitivity at complex variant loci, dramatically outperforming MuTect, a well-established pipeline. Conclusion By designing novel suffix-array based SNV calling methods, we have developed a practical SNV calling software, GeDi, that can characterise SNVs at complex variant loci and at low allele frequency thus increasing the repertoire of detectable SNVs in tumour genomes. We expect GeDi to find use cases in targeted-deep sequencing analysis, and to serve as a replacement and improvement over previous suffix-array based SNV calling methods.

关键词： Variant calling SNV Cancer Genomics suffix array

来源：评论

学校读者我要写书评

暂无评论

Dynamic extended suffix arrays

引用

JOURNAL OF DISCRETE ALGORITHMS 2010年第2期8卷 241-257页

作者： Salson, M. Lecroq, T. Leonard, M. Mouchard, L. Univ Rouen LITIS EA 4108 F-76821 Mont St Aignan France Kings Coll London Dept Comp Sci Algorithm Grp Design London WC2R 2LS England

The suffix tree data structure has been intensively described, studied and used in the eighties and nineties, its linear-time construction counterbalancing his space-consuming requirements. An equivalent data structure, the suffix array, has been described by Manber and Myers in 1990. This space-economical structure has been neglected during more than a decade, its construction being too slow. Since 2003, several linear-time suffix array construction algorithms have been proposed, and this structure has slowly replaced the suffix tree in many string processing problems. All these constructions are building the suffix array from the text, and any edit operation on the text leads to the construction of a brand new suffix array. In this article, we are presenting an algorithm that modifies the suffix array and the Longest Common Prefix (LCP) array when the text is edited (insertion, substitution or deletion of a letter or a factor). This algorithm is based on a recent four-stage algorithm developed for dynamic Burrows-Wheeler Transforms (BWT). For minimizing the space complexity, we are sampling the suffix array, a technique used in BWT-based compressed indexes. We furthermore explain how this technique can be adapted for maintaining a sample of the Extended suffix array, containing a sample of the suffix array, a sample of the Inverse suffix array and the whole LCP array. Our practical experiments show that it operates very well in practice, being quicker than the fastest suffix array construction algorithm. (C) 2009 Published by Elsevier B.V.

关键词： Dynamic suffix array Edit operations Algorithm design Self-index data structures FM-index

来源：评论

学校读者我要写书评

暂无评论

gsufsort: constructing suffix arrays, LCP arrays and BWTs for string collections

引用

ALGORITHMS FOR MOLECULAR BIOLOGY 2020年第1期15卷 18-18页

作者： Louza, Felipe A. Telles, Guilherme P. Gog, Simon Prezza, Nicola Rosone, Giovanna Univ Fed Uberlandia Fac Engn Eletr Uberlandia MG Brazil Univ Estadual Campinas Inst Computacao Campinas Brazil eBay Inc San Jose CA USA Univ Rome LUISS Guido Carli Rome Italy Univ Pisa Dipartimento Informat Pisa Italy

Background The construction of a suffix array for a collection of strings is a fundamental task in Bioinformatics and in many other applications that process strings. Related data structures, as the Longest Common Prefix array, the Burrows-Wheeler transform, and the document array, are often needed to accompany the suffix array to efficiently solve a wide variety of problems. While several algorithms have been proposed to construct the suffix array for a single string, less emphasis has been put on algorithms to construct suffix arrays for string collections. Result In this paper we introduce gsufsort, an open source software for constructing the suffix array and related data indexing structures for a string collection withNsymbols inO(N) time. Our tool is written in ANSI/C and is based on the algorithm gSACA-K(Louza et al. in Theor Comput Sci 678:22-39, 2017), the fastest algorithm to construct suffix arrays for string collections. The tool supports large fasta, fastq and text files with multiple strings as input. Experiments have shown very good performance on different types of strings. Conclusions gsufsort is a fast, portable, and lightweight tool for constructing the suffix array and additional data structures for string collections.

关键词： suffix array LCP array Burrows-Wheeler transform Document array String collections

来源：评论

学校读者我要写书评

暂无评论

When Indexing Equals Compression: Experiments with Compressing suffix arrays and Applications

引用

ACM TRANSACTIONS ON ALGORITHMS 2006年第4期2卷 611-639页

作者： Foschini, Luca Grossi, Roberto Gupta, Ankur Vitter, Jeffrey Scott Scuola Super Sant Anna I-56127 Pisa Italy Univ Pisa Dipartimento Informat I-56127 Pisa Italy Duke Univ Dept Comp Sci Ctr Geometr & Biol Comp Durham NC 27708 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

We report on a new experimental analysis of high-order entropy-compressed suffix arrays, which retains the theoretical performance of previouswork and represents an improvement in practice. Our experiments indicate that the resulting text index offers state-of-the-art compression. In particular, we require roughly 20% of the original text size-without requiring a separate instance of the text. We can additionally use a simple notion to encode and decode block-sorting transforms (such as the Burrows-Wheeler transform), achieving a compression ratio comparable to that of bzip2. We also provide a compressed representation of suffix trees (and their associated text) in a total space that is comparable to that of the text alone compressed with gzip.

关键词： Algorithms Design Experimentation Theory Entropy text indexing Burrows-Wheeler Transform suffix array

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：