12,127 research outputs found
Approximate pattern matching on elastic-degenerate text
No full textAn elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent a multiple alignment of several closely-related sequences (e.g., pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length m in an elastic-degenerate text. There exists a non-combinatorial O(nm1.381+N)-time algorithm to solve this problem on-line [1]. In this paper, we study the same problem under the edit distance model and present an O(k2mG+kN)-time and O(m)-space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O(kmG+kN)-time and O(m)-space algorithm for solving the problem under Hamming distance
Pattern matching on elastic-degenerate text with errors
No full textAn elastic-degenerate string is a sequence of n sets of strings of total length N. It has been introduced to represent a multiple alignment of several closely-related sequences (e.g. pan-genome) compactly. In this representation, substrings of these sequences that match exactly are collapsed, while in positions where the sequences differ, all possible variants observed at that location are listed. The natural problem that arises is finding all matches of a deterministic pattern of length m in an elastic-degenerate text. There exists an O(nm2 + N) -time algorithm to solve this problem on-line after a pre-processing stage with time and space O(m). In this paper, we study the same problem under the edit distance model and present an O(k2mG+kN) -time and O(m)-space algorithm, where G is the total number of strings in the elastic-degenerate text and k is the maximum edit distance allowed. We also present a simple O(kmG+kN)-time and O(m)-space algorithm for Hamming distance
MARS: Improving multiple circular sequence alignment using refined sequences
No full textAvailability of data and materials:
The datasets generated during and/or analysed during the current study are available in the GitHub repository. Project name: MARS Project home page: https://github.com/lorrainea/mars Operating system: GNU/Linux Programming language: C++ Other requirements: N/A License: GNU GPLBackground: A fundamental assumption of all widely-used multiple sequence alignment techniques is that the left- and right-most positions of the input sequences are relevant to the alignment. However, the position where a sequence starts or ends can be totally arbitrary due to a number of reasons: arbitrariness in the linearisation (sequencing) of a circular molecular structure; or inconsistencies introduced into sequence databases due to different linearisation standards. These scenarios are relevant, for instance, in the process of multiple sequence alignment of mitochondrial DNA, viroid, viral or other genomes, which have a circular molecular structure. A solution for these inconsistencies would be to identify a suitable rotation (cyclic shift) for each sequence; these refined sequences may in turn lead to improved multiple sequence alignments using the preferred multiple sequence alignment program. Results: We present MARS, a new heuristic method for improving Multiple circular sequence Alignment using Refined Sequences. MARS was implemented in the C++ programming language as a program to compute the rotations (cyclic shifts) required to best align a set of input sequences. Experimental results, using real and synthetic data, show that MARS improves the alignments, with respect to standard genetic measures and the inferred maximum-likelihood-based phylogenies, and outperforms state-of-the-art methods both in terms of accuracy and efficiency. Our results show, among others, that the average pairwise distance in the multiple sequence alignment of a dataset of widely-studied mitochondrial DNA sequences is reduced by around 5% when MARS is applied before a multiple sequence alignment is performed. Conclusions: Analysing multiple sequences simultaneously is fundamental in biological research and multiple sequence alignment has been found to be a popular method for this task. Conventional alignment techniques cannot be used effectively when the position where sequences start is arbitrary. We present here a method, which can be used in conjunction with any multiple sequence alignment program, to address this problem effectively and efficiently.LAKA is supported by an EPSRC grant (Doctoral Training Grant #EP/M50788X/1)
Jaccard Median for ego-network segmentation
No full textAn ego-network is a graph representing the interactions of a node (ego) with its neighbors and the interactions among those neighbors. A sequence of ego-networks having the same ego can thus model the evolution of these interactions over time. We introduce the problem of segmenting a sequence of ego-networks into k segments, for any given integer k. Each segment is represented by a summary network, and the goal is to minimize the total loss of representing k segments by k summaries. The problem allows partitioning the sequence into homogeneous segments with respect to the activities or properties of the ego (e.g., to identify time periods when a user acquired different circles of friends in a social network) and to compactly represent each segment with a summary. The main challenge is to construct a summary that represents a collection of ego-networks with minimum loss. To address this challenge, we employ Jaccard Median (JM), a well-known NP-hard problem for summarizing sets, for which, however, no effective and efficient algorithms are known. We develop a series of algorithms for JM offering different effectiveness/efficiency trade-offs: (I) an exact exponential-time algorithm, based on Mixed Integer Linear Programming and (II) exact and approximation polynomial-time algorithms for minimizing an upper bound of the objective function of JM. By building upon these results, we design two algorithms for segmenting a sequence of ego-networks that are effective, as shown experimentally
libFLASM: A software library for fixed-length approximate string matching
No full textAvailability of data and materials:
The datasets generated during and/or analysed during the current study are available at the GitHub repository. Project name: libFLASM. Project home page: https://github.com/webmasterar/libFLASM . Operating system: GNU/Linux. Programming language: C++. Other requirements: N/A. License: GNU GPLBackground:
Approximate string matching is the problem of finding all factors of a given text that are at a distance at most k from a given pattern. Fixed-length approximate string matching is the problem of finding all factors of a text of length n that are at a distance at most k from any factor of length ℓ of a pattern of length m. There exist bit-vector techniques to solve the fixed-length approximate string matching problem in time and space under the edit and Hamming distance models, where w is the size of the computer word; as such these techniques are independent of the distance threshold k or the alphabet size. Fixed-length approximate string matching is a generalisation of approximate string matching and, hence, has numerous direct applications in computational molecular biology and elsewhere.
Results:
We present and make available libFLASM, a free open-source C++ software library for solving fixed-length approximate string matching under both the edit and the Hamming distance models. Moreover we describe how fixed-length approximate string matching is applied to solve real problems by incorporating libFLASM into established applications for multiple circular sequence alignment as well as single and structured motif extraction. Specifically, we describe how it can be used to improve the accuracy of multiple circular sequence alignment in terms of the inferred likelihood-based phylogenies; and we also describe how it is used to efficiently find motifs in molecular sequences representing regulatory or functional regions. The comparison of the performance of the library to other algorithms show how it is competitive, especially with increasing distance thresholds.
Conclusions:
Fixed-length approximate string matching is a generalisation of the classic approximate string matching problem. We present libFLASM, a free open-source C++ software library for solving fixed-length approximate string matching. The extensive experimental results presented here suggest that other applications could benefit from using libFLASM, and thus further maintenance and development of libFLASM is desirable.LAKA is supported by an EPSRC grant (Doctoral Training Grant #EP/M50788X/1). AR is supported by the Graduate Teaching Scholarship scheme of the Department of Informatics at King’s College London
Text Indexing for Long Patterns: Anchors are All you Need
No full textPVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at https://github.com/lorrainea/BDA- index.Copyright © 2023 the owner/author(s). In many real-world database systems, a large fraction of the data is represented by strings: sequences of letters over some alphabet. This is because strings can easily encode data arising from different sources. It is often crucial to represent such string datasets in a compact form but also to simultaneously enable fast pattern matching queries. This is the classic text indexing problem. The four absolute measures anyone should pay attention to when designing or implementing a text index are: (i) index space; (ii) query time; (iii) construction space; and (iv) construction time. Unfortunately, however, most (if not all) widely-used indexes (e.g., suffix tree, suffix array, or their compressed counterparts) are not optimized for all four measures simultaneously, as it is difficult to have the best of all four worlds. Here, we take an important step in this direction by showing that text indexing with locally consistent anchors (lc-anchors) offers remarkably good performance in all four measures, when we have at hand a lower bound l on the length of the queried patterns --- which is arguably a quite reasonable assumption in practical applications. Specifically, we improve on the construction of the index proposed by Loukides and Pissis, which is based on bidirectional string anchors (bd-anchors), a new type of lc-anchors, by: (i) designing an average-case linear-time algorithm to compute bd-anchors; and (ii) developing a semi-external-memory implementation to construct the index in small space using near-optimal work. We then present an extensive experimental evaluation, based on the four measures, using real benchmark datasets. The results show that, for long patterns, the index constructed using our improved algorithms compares favorably to all classic indexes: (compressed) suffix tree; (compressed) suffix array; and the FM-index.European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements No 872539 and 956229, respectively; and by UKRI through REPHRAIN (EP/V011189/1)
Minimizing the Minimizers via Alphabet Reordering
No full textConference paper presented at the 35th Annual Symposium on Combinatorial Pattern Matching (CPM 2024),
Fukuoka, Japan, 25-27 Jun 2024.Minimizers sampling is one of the most widely-used mechanisms for sampling strings [Roberts et al., Bioinformatics 2004]. Let S = S[1]… S[n] be a string over a totally ordered alphabet Σ. Further let w ≥ 2 and k ≥ 1 be two integers. The minimizer of S[i..i+w+k-2] is the smallest position in [i,i+w-1] where the lexicographically smallest length-k substring of S[i..i+w+k-2] starts. The set of minimizers over all i ∈ [1,n-w-k+2] is the set ℳ_{w,k}(S) of the minimizers of S.
We consider the following basic problem:
Given S, w, and k, can we efficiently compute a total order on Σ that minimizes |ℳ_{w,k}(S)|?
We show that this is unlikely by proving that the problem is NP-hard for any w ≥ 3 and k ≥ 1. Our result provides theoretical justification as to why there exist no exact algorithms for minimizing the minimizers samples, while there exists a plethora of heuristics for the same purpose.Verbeek, Hilde: Supported by a Constance van Eeden Fellowship.
Pissis, Solon P.: Supported by the PANGAIA and ALPACA projects that have received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreements No 872539 and 956229, respectively
A new species of Aleurolobus Quaintance et Baker (Homoptera, Aleyrodidae) from Southern Europe.
No full textAleurolobus teucrii n. sp. is described from southern Italy and the Maltese Islands (Central Mediterranean). The species seems to be monophagous on Teucrium fruticans L. A key to the European species of this genus (A. niloticus Priesner et Hosny, A. olivinus (Silvestri), A. wunni (Ryberg) and A. teucrii n. sp.) is provided.peer-reviewe
Mosquito Larvicidal Constituents from Lantana Viburnoides SP Viburnoides Var Kisi (A. rich) Verdc (Verbenaceae).
No full text\ud
\ud
Lantana viburnoides sp viburnoides var kisi is used in Tanzania ethnobotanically to repel mosquitoes as well as in traditional medicine for stomach ache relief. Bioassay-guided fractionation and subtraction bioassays of the dichloromethane extract of the root barks were carried out in order to identify the bioactive components for controlling Anopheles gambiae s.s. mosquito larvae. Twenty late III or early IV instar larvae of An. gambiae s.s. were exposed to various concentrations of the plant extracts, fractions, blends and pure compounds, and were assayed in the laboratory by using the protocol of WHO 1996. Mean mortalities were compared using Dunnett's test (p < 0.05) and lethal concentration calculated by Lackfit Inversel of the SAS programme. The crude extract (LC50 = 7.70 ppm in 72 h) and fractions exhibited different level of mosquito larvicidal activity with subtraction of some fractions resulting in activity enhancement. The active fractions contained furanonaphthaquinones regio-isomers (LC50 = 5.48-5.70 ppm in 72 h) and the lantadene triterpenoid camaric acid (LC50 = 6.19 ppm in 72 h) as active principles while the lupane triterpenoid betulinic acid (LC50 < 10 ppm in 72 h) was obtained from the least active fraction. Crude extracts and some fractions had higher or comparable larvicidal activity to the pure compounds. These results demonstrate that L. viburnoides sp viburnoides var kisi extracts may serve as larvicides for managing various mosquito habitats even in their semi-purified form. The isolated compounds can be used as distinct markers in the active extracts or plant materials belonging to the genus Lantana
U-Index: A Universal Indexing Framework for Matching Long Patterns
No full textA related version of this article is available at arXiv:2502.14488v3 [cs.DS] (https://arxiv.org/abs/2502.14488). Comments: SEA-2025 version. 18 pages, 6 figures, code available at https://github.com/u-index/u-index-rs . ACM classes: F.2.2; J.3. Submission history: From: Ragnar Groot Koerkamp: [v1] Thu, 20 Feb 2025 12:09:34 UTC (383 KB); [v2] Fri, 21 Feb 2025 13:35:43 UTC (383 KB); [v3] Tue, 27 May 2025 12:05:04 UTC (459 KB).Motivation. Text indexing is a fundamental and well-studied problem. Classic solutions to this problem either replace the original text with a compressed representation, e.g., the FM-index and its variants, or keep it uncompressed but attach some redundancy - an index - to accelerate matching, e.g., the suffix array. The former solutions thus retain excellent compressed space, but are practically slow to construct and query. The latter approaches, instead, sacrifice space efficiency but are typically faster; for example, the suffix array takes much more space than the text itself for commonly used alphabets, like ASCII or DNA, but it is very fast to construct and query.
Methods. In this paper, we show that efficient text indexing can be achieved using just a small extra space on top of the original text, provided that the query patterns are sufficiently long. More specifically, we develop a new indexing paradigm in which a sketch of a query pattern is first matched against a sketch of the text. Once candidate matches are retrieved, they are verified using the original text. This paradigm is thus universal in the sense that it allows us to use any solution to index the sketched text, like a suffix array, FM-index, or r-index.
Results. We explore both the theory and the practice of this universal framework. With an extensive experimental analysis, we show that, surprisingly, universal indexes can be constructed much faster than their unsketched counterparts and take a fraction of the space, as a direct consequence of (i) having a lower bound on the length of patterns and (ii) working in sketch space. Furthermore, these data structures have the potential of retaining or even improving query time, because matching against the sketched text is faster and verifying candidates can be theoretically done in constant time per occurrence (or, in practice, by short and cache-friendly scans of the text).
Finally, we discuss some important applications of this novel indexing paradigm to computational biology. We hypothesize that such indexes will be particularly effective when the queries are sufficiently long, and so we demonstrate applications in long-read mapping.Gabriele Fici: Supported by MUR project PRIN 2022 APML – 20229BCXNW, funded
by the European Union -– Mission 4 “Education and Research” C2 - Investment 1.1. CUP
Master_B53D23012910006.
Ragnar Groot Koerkamp: ETH Research Grant ETH-1721-1 to Gunnar Rätsch.
Rob Patro: NIH grant award number R01HG009937, NSF award CNS-1763680 and grants 252586 and
2024342821 from the Chan Zuckerberg Initiative DAF, an advised fund of Silicon Valley Community
Foundation. RP is a co-founder of Ocean Genomics, Inc.
Giulio Ermanno Pibiri: European Union’s Horizon Europe research and innovation programme
(EFRA project, Grant Agreement Number 101093026). This work was also partially supported by
DAIS – Ca’ Foscari University of Venice within the IRIDE program.
Solon P. Pissis: Supported by the PANGAIA and ALPACA projects that have received funding
from the European Union’s Horizon 2020 research and innovation programme under the Marie
Skłodowska-Curie grant agreements No 872539 and 956229, respectively
- …
