Search

This study introduces a pioneering approach to automate the creation of search schemes for lossless approximate pattern matching. Search schemes are combinatorial structures that define a series of searches over a partitioned pattern. Each search specifies the processing order of these parts and the cumulative lower and upper bounds on the number of errors in each part of the pattern. Together, these searches ensure the identification of all approximate occurrences of a search pattern within a predefined limit of k errors. While existing literature offers designed schemes for up to k = 4 errors, designing search schemes for larger k values incurs escalating computational costs. Our method integrates a greedy algorithm and a novel Integer Linear Programming (ILP) formulation to design efficient search schemes for up to k = 7 errors. Comparative analyses demonstrate the superiority of our ILP-optimal schemes over alternative strategies in both theoretical and practical contexts. Additionally, we propose a dynamic scheme selection technique tailored to specific search patterns, further enhancing efficiency. Combined, this yields runtime reductions of up to 53% for higher k values. To facilitate search scheme generation, we present Hato, an open-source software tool (AGPL-3.0 license) employing the greedy algorithm and utilizing CPLEX for ILP solving. Furthermore, we introduce Columba 1.2, an open-source lossless read-mapper (AGPL-3.0 license) implemented in C++. Columba surpasses existing state-of-the-art tools by identifying all approximate occurrences of 100,000 Illumina reads (150 bp) in the human reference genome within 24 seconds (maximum edit distance of 4) and 75 seconds (maximum edit distance of 6) using a single CPU core. Notably, our study showcases Columba's capability to align 100,000 reads of length 50, with high error rates and up to an edit distance of 7, in a mere 2 hours and 15 minutes. This achievement is unmatched by other lossless aligners, which require over 3 hours for edit distance 5 alignments. Moreover, Columba exhibits a mapping rate four times higher than that of a lossy tool for this dataset.

Due to the increasing availability of high-quality genome sequences, pan-genomes are gradually replacing single consensus reference genomes in many bioinformatics pipelines to better capture genetic diversity. Traditional bioinformatics tools using the FM-index face memory limitations with such large genome collections. Recent advancements in run-length compressed indices like Gagie et al.'s r-index and Nishimoto and Tabei's move structure, alleviate memory constraints but focus primarily on backward search for MEM-finding. Arakawa et al.'s br-index initiates complete approximate pattern matching using bidirectional search in run-length compressed space, but with significant computational overhead due to complex memory access patterns. We introduce b-move, a novel bidirectional extension of the move structure, enabling fast, cache-efficient bidirectional character extensions in run-length compressed space. It achieves bidirectional character extensions up to 8 times faster than the br-index, closing the performance gap with FM-index-based alternatives, while maintaining the br-index's favorable memory characteristics. For example, all available complete E. coli genomes on NCBI's RefSeq collection can be compiled into a b-move index that fits into the RAM of a typical laptop. Thus, b-move proves practical and scalable for pan-genome indexing and querying. We provide a C++ implementation of b-move, supporting efficient lossless approximate pattern matching including locate functionality, available at https://github.com/biointec/b-move under the AGPL-3.0 license.

MONI (Rossi et al., JCB 2022) is a BWT-based compressed index for computing the matching statistics and maximal exact matches (MEMs) of a pattern (usually a DNA read) with respect to a highly repetitive text (usually a database of genomes) using two operations: LF-steps and longest common extension (LCE) queries on a grammar-compressed representation of the text. In practice, most of the operations are constant-time LF-steps but most of the time is spent evaluating LCE queries. In this paper we show how (a variant of) the latter can be evaluated lazily, so as to bound the total time MONI needs to process the pattern in terms of the number of MEMs between the pattern and the text, while maintaining logarithmic latency.

Background: Pan-genome graphs are gaining importance in the field of bioinformatics as data structures to represent and jointly analyze multiple genomes. Compacted de Bruijn graphs are inherently suited for this purpose, as their graph topology naturally reveals similarity and divergence within the pan-genome. Most state-of-the-art pan-genome graphs are represented explicitly in terms of nodes and edges. Recently, an alternative, implicit graph representation was proposed that builds directly upon the unidirectional FM-index. As such, a memory-efficient graph data structure is obtained that inherits the FM-index' backward search functionality. However, this representation suffers from a number of shortcomings in terms of functionality and algorithmic performance., Results: We present a data structure for a pan-genome, compacted de Bruijn graph that aims to address these shortcomings. It is built on the bidirectional FM-index, extending the ability of its unidirectional counterpart to navigate and search the graph in both directions. All basic graph navigation steps can be performed in constant time. Based on these features, we implement subgraph visualization as well as lossless approximate pattern matching to the graph using search schemes. We demonstrate that we can retrieve all occurrences corresponding to a read within a certain edit distance in a very efficient manner. Through a case study, we show the potential of exploiting the information embedded in the graph's topology through visualization and sequence alignment., Conclusions: We propose a memory-efficient representation of the pan-genome graph that supports subgraph visualization and lossless approximate pattern matching of reads against the graph using search schemes. The C++ source code of our software, called Nexus, is available at https://github.com/biointec/nexus under AGPL-3.0 license., (© 2023. The Author(s).)

Background: To investigate progression free survival (PFS), local control (LC) and overall survival (OS) outcomes for patients treated with spine hypofractionated stereotactic ablative radiotherapy (SABR) and to evaluate possible predictors of rapid progression in view of a correct patient selection for this potentially curative SABR., Materials and Methods: A cohort of 59 patients with spinal metastases were treated with SABR. Patient selection criteria were the following: histologically proven diagnosis of a solid tumor, a World Health Organization (WHO) score ≤ 2, life expectancy > 6 months, Spinal Instability Neoplastic Score (SINS) ≤ 12 points and presenting with radically treated oligometastatic disease (≤5 lesions) or stable polymetastatic disease with an oligoprogressive lesion., Results: From March 2015 to June 2019, 59 patients were treated with Linac-based SABR to 64 spinal metastases with a median follow-up of 55 months. SABR was standard delivered every other day in 3 to 10 fractions with median prescription dose of 27 Gy (range 21-49 Gy).The 1-,2- and 5-year PFS was 98%, 85% and 75% for all patients. OS at 5 years for all patients was 92%. Metachronous lesions (p < 0.01; HR = 7.1) and oligometastatic (vs. oligoprogressive) lesions (p = 0.02; HR = 0.3) were associated with higher PFS in uni- and multivariate Cox regression analysis. No significant predictors in multivariate analysis were demonstrated for rapid progressors.Vertebral compression fractures developed de novo in 6.3% (4/64) of cases. The median time to fracture was 11 months (range 7-15) after treatment. No other adverse events ≥ 3 grade were observed., Conclusions: Tumor control and toxicity after high-dose hypofractionated SABR was evaluated in patients with spinal oligometastases. High rates of efficacy and minimal toxicity were demonstrated. Oligometastatic patients with metachronous spinal metastases seem to benefit the most from SABR., Competing Interests: The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper., (© 2020 Published by Elsevier B.V. on behalf of European Society for Radiotherapy and Oncology.)

Background and Purpose: The TRENDY trial is an international multi-center phase-II study, randomizing hepatocellular carcinoma (HCC) patients between transarterial chemoembolization (TACE) and stereotactic body radiation therapy (SBRT) with a target dose of 48-54 Gy in six fractions. The radiotherapy quality assurance (QA) program, including prospective plan feedback based on automated treatment planning, is described and results are reported., Materials and Methods: Scans of a single patient were used as a benchmark case. Contours submitted by nine participating centers were compared with reference contours. The subsequent planning round was based on a single set of contours. A total of 20 plans from participating centers, including 12 from the benchmark case, 5 from a clinical pilot and 3 from the first study patients, were compared to automatically generated VMAT plans., Results: For the submitted liver contours, Dice Similarity Coefficients (DSC) with the reference delineation ranged from 0.925 to 0.954. For the GTV, the DSC varied between 0.721 and 0.876. For the 12 plans on the benchmark case, healthy liver normal-tissue complication probabilities (NTCPs) ranged from 0.2% to 22.2% with little correlation between NCTP and PTV-D95% (R 2  < 0.3). Four protocol deviations were detected in the set of 20 treatment plans. Comparison with co-planar autoVMAT QA plans revealed these were due to too high target dose and suboptimal planning. Overall, autoVMAT resulted in an average liver NTCP reduction of 2.2 percent point (range: 16.2 percent point to -1.8 percent point, p = 0.03), and lower doses to the healthy liver (p < 0.01) and gastrointestinal organs at risk (p < 0.001)., Conclusions: Delineation variation resulted in feedback to participating centers. Automated treatment planning can play an important role in clinical trials for prospective plan QA as suboptimal plans were detected., (Copyright © 2017 Elsevier B.V. All rights reserved.)

Belgium counts more than a million dogs and at least two million cats, of which many are carrying zoonotic nematodes of the genus Toxocara. Environmental contamination with worm eggs is considered the key transmission route from animals to humans, and mainly young children are at risk. Contamination of soil with Toxocara eggs has been reported from all over the world, but data are lacking for Belgium. In this study, faecal contamination and the presence of Toxocara eggs in sand were investigated in sandpits of public playgrounds and kindergartens in Flanders (Northern Belgium). Faeces, of which 85% originated from cats, were found in about one third of the public playgrounds and one fifth of the kindergartens. Toxocara eggs were found in 12% of the faecal samples, in 14% of the public sandpits, and in 2% of the sandpits of kindergartens. These data indicate that environmental contamination with Toxocara exists in urban areas in Belgium, and that cats are most likely the main source., (Copyright © 2016 The Authors. Published by Elsevier B.V. All rights reserved.)

Objective: To study the effect of long-term extracorporeal membrane oxygenation (ECMO) support on neutrophil function., Design: A prospective, clinical investigation., Setting: A pediatric intensive care unit., Patients: Four groups of patients: ECMO group 1, newborns after 1 day of ECMO support (n = 10); ECMO group 2, newborns after 5 days of ECMO support (n = 6); group 3, normal newborns (n = 20); group 4, normal adults (n = 30)., Interventions: Two mL of heparinized blood was obtained from patients in each group. A modification of the Smith and Rommel technique was used to measure neutrophil phagocytosis and killing utilizing live Candida tropicalis as the test organism. Neutrophils were incubated for 90 mins in normal adult serum with live Candida. Viability of Candida after phagocytosis was tested by vital fluorochrome staining. Phagocytic index (the number of neutrophils with intracytoplasmic Candida divided by the total neutrophils) and candidicidal ratio (neutrophils with dead Candida divided by total neutrophils with Candida) were determined daily., Measurements and Main Results: Neutrophils from ECMO group 1 (day 1) and ECMO group 2 (day 5) patients had significantly higher phagocytosis indices (72.8 +/- 20 and 76 +/- 18) and candidicidal ratios (0.15 +/- 0.1 and 0.16 +/- 0.09) compared with neutrophils from group 3 patients (normal neonates) (64 +/- 7 and 0.06 +/- 0.04). The phagocytosis indices were significantly lower in neutrophils from ECMO group 1 (day 1) and ECMO group 2 (day 5) patients compared with group 4 (adults) patients (86 +/- 9). However, the candidicidal ratios in neutrophils from ECMO groups 1 and 2 (ECMO day 1 and day 5) patients were equal to that value in group 4 (adults) (0.10 +/- 0.04). ECMO support for 5 days (ECMO group 2 vs. group 1) did not significantly change either the phagocytosis index or candidicidal ratio., Conclusions: Phagocytosis and intracellular killing by neutrophils of ECMO-supported neonates were significantly greater than those values found in normal newborns. ECMO support for 5 days produced no significant changes in neutrophil phagocytosis or killing.