20 papers · ranked by Valyu relevance
Robert Susik, Szymon Grabowski, Kimmo Fredriksson
We consider the classical exact multiple string matching problem. Our solution is based on q-grams combined with pattern superimposition, bit-parallelism and alphabet size reduction. We discuss the pros and cons of the various alternatives of how to achieve best combination. Our method is closely related to previous…
Kapil Kumar Soni, Akhtar Rasool, Siddhartha Bhattacharyya
This article presents efficient quantum solutions for exact multiple pattern matching to process the biological sequences. The classical solution takes Ο(mN) time for matching m patterns over N sized text database. The quantum search mechanism is a core for pattern matching, as this reduces time complexity and achieves…
Johannes Fischer, Travis Gagie, Paweł Gawrychowski, Tomasz Kociumaka
We generalize Karp-Rabin string matching to handle multiple patterns in O(n log n + m) time and O(s) space, where n is the length of the text and m is the total length of the s patterns, returning correct answers with high probability. As a prime application of our algorithm, we show how to approximate the LZ77 parse…
Geonmo Gu, Siwoo Song, Simone Faro, Thierry Lecroq + 1 more
Cartesian tree matching is the problem of finding all substrings in a given text which have the same Cartesian trees as that of a given pattern. In this paper, we deal with Cartesian tree matching for the case of multiple patterns. We present two fingerprinting methods, i.e., the parent-distance encoding and the binary…
Rick Beeloo, Ragnar Groot Koerkamp
Searching short DNA patterns such as barcodes, primers, or CRISPR spacers within sequencing reads or genomes is a fundamental task in bioinformatics. These problems are instances of multiple approximate string matching (MASM) [1], which requires locating all occurrences with up to k errors of multiple patterns of…
Daniel Liu
Next-generation sequencing technologies create large, multiplexed DNA sequences that require preprocessing before any further analysis. Part of this preprocessing includes demultiplexing and trimming sequences. Although there are many existing tools that can handle these preprocessing steps, they cannot be easily…
S. Kanchana, G. Balakrishnan
Palm-print based individual identification is regarded as an effectual method for identifying persons with high confidence. Palm-print with larger inner surface of hand contains many features such as principle lines, ridges, minutiae points, singular points, and textures. Feature based pattern matching has faced the…
Daniel Liu, Sven Rahmann
Next-generation sequencing technologies create large, multiplexed DNA sequences that require preprocessing before any further analysis. Part of this preprocessing includes demultiplexing and trimming sequences. Although there are many existing tools that can handle these preprocessing steps, they cannot be easily…
Satoshi Egi
This paper proposes a pattern-matching system that enables nonlinear pattern-matching against unfree data types. The system allows multiple occurrences of the same variables in a pattern, multiple results of pattern-matching and modularization of the way of pattern-matching for each data type at the same time. It…
Ping Zeng, Qingping Tan, Xiankai Meng, Zeming Shao + 5 more
'Ying Yan' 'Wei Cao' 'Jianjun Xu' 'Francesco Pappalardo'] In this paper, based on our previous multi-pattern uniform resource locator (URL) binary-matching algorithm called HEM, we propose an improved multi-pattern matching algorithm called MH that is based on hash tables and binary tables. The MH algorithm can be…
HyunJin Kim, Kang-Il Choi, Sang-Il Choi, Francesco Pappalardo
This paper proposes a memory-efficient bit-split string matching scheme for deep packet inspection (DPI). When the number of target patterns becomes large, the memory requirements of the string matching engine become a critical issue. The proposed string matching scheme reduces the memory requirements using the…
Pramesh Shakya, Ardalan Naseri, Degui Zhi, Shaojie Zhang
Positional Burrows-Wheeler Transform (PBWT) is a data structure that supports efficient algorithms for finding matching segments in a panel of haplotypes. It is of interest to study the composite patterns of multiple matching segments or blocks arranged contiguously along a same haplotype as they can indicate…
HyunJin Kim, Kang-Il Choi, Yongtang Shi
This paper proposes a pipelined non-deterministic finite automaton (NFA)-based string matching scheme using field programmable gate array (FPGA) implementation. The characteristics of the NFA such as shared common prefixes and no failure transitions are considered in the proposed scheme. In the implementation of the…
Travis Gagie, Simon J. Puglisi
The rapid advance of DNA sequencing technologies has yielded databases of thousands of genomes. To search and index these databases effectively, it is important that we take advantage of the similarity between those genomes. Several authors have recently suggested searching or indexing only one reference genome and the…
Tim Anderson, Travis J Wheeler
Pattern matching is a key step in a variety of biological sequence analysis pipelines. The FM-index is a compressed data structure for pattern matching, with search run time that is independent of the length of the database text. We present AvxWindowedFMindex (AWFM-index), an open-source, thread-parallel FM-index…
Hongyi Xin, Jeremie Kim, Sunny Nahar, Carl Kingsford + 2 more
Approximate String Matching is a pivotal problem in the field of computer science. It serves as an integral component for many string algorithms, most notably, DNA read mapping and alignment. The improved LV algorithm proposes an improved dynamic programming strategy over the banded Smith-Waterman algorithm but suffers…
Simone Faro
In this short note we present a comprehensive bibliography for the online exact string matching problem. The problem consists in finding all occurrences of a given pattern in a text. It is an extensively studied problem in computer science, mainly due to its direct applications to such diverse areas as text, image and…
Martin Priessner, Anna Tomberg, Jon Paul Janet, Richard J. Lewis + 2 more
In the pursuit of improved compound identification and database search tasks, this study explores Heteronuclear Single Quantum Coherence (HSQC) spectra simulation and matching methodologies. HSQC spectra serve as unique molecular fingerprints, enabling a valuable balance of data collection time and information…
Andrew Hoover, Martin Spale, Brian Lahue, Danny Bitton
To solve recurring problems in drug discovery, matched molecular pair (MMP) analysis is used to understand relationships between chemical structure and function. For the MMP analysis of large datasets (>10,000 compounds), available tools lack flexible search and visualization functionality and require computational…
David Degnan, Kevin Zemaitis, Logan Lewis, Lee Ann McCue + 5 more
Due to its speed, accuracy, and adaptability to various sample types, matrix-assisted laser desorption/ionization mass spectrometry (MALDI-MS) has become a popular method to identify molecular isotope profiles from biological samples. Often MALDI-MS data does not include tandem MS fragmentation data, and thus the…