545 research outputs found
The open-closed mod-minimizer algorithm
No full textSampling algorithms that deterministically select a subset of k-mers are an important building block in bioinformat-ics applications. For example, they are used to index large textual collections, like DNA, and to compare sequences quickly. In such applications, a sampling algorithm is required to select one k-mer out of every window of w consecu-tive k-mers. The folklore and most used scheme is the random minimizer that selects the smallest k-mer in the win-dow according to some random order. This scheme is remarkably simple and versatile, and has a density (expected fraction of selected k-mers) of 2/(w+1) . In practice, lower density leads to faster methods and smaller indexes, and it turns out that the random minimizer is not the best one can do. Indeed, some schemes are known to approach optimal density 1/w when k ->infinity , like the recently introduced mod-minimizer (Groot Koerkamp and Pibiri, WABI 2024). In this work, we study methods that achieve low density when k <= w . In this small-k regime, a practical method with provably better density than the random minimizer is the miniception (Zheng et al., Bioinformatics 2021). This method can be elegantly described as sampling the smallest closed sycnmer (Edgar, PeerJ 2021) in the window according to some random order. We show that extending the miniception to prefer sampling open syncmers yields much better density. This new method-the open-closed minimizer-offers improved density for small k <= w while being as fast to compute as the random minimizer. Compared to methods based on decycling sets, that achieve very low density in the small-k regime, our method has comparable density while being computation-ally simpler and intuitive. Furthermore, we extend the mod-minimizer to improve density of any scheme that works well for small k to also work well when k>w is large. We hence obtain the open-closed mod-minimizer, a practical method that improves over the mod-minimizer for all
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
High mortality after ALPPS for perihilar cholangiocarcinoma: case-control analysis including the first series from the international ALPPS registry.
No full textINTRODUCTION:
Resection of perihilar cholangiocarcinoma (PHC) entails high-risk surgery with postoperative mortality reported up to 18%, even in specialized centers. The aim of this study was to compare outcomes of PHC patients who underwent associating liver partition and portal vein ligation for staged hepatectomy (ALPPS) to patients who underwent resection without ALPPS.
METHODS:
All patients who underwent ALPPS for PHC were identified from the international ALPPS registry and matched controls were selected from a standard resection cohort from two centers based on future remnant liver size. Outcomes included morbidity, mortality, and overall survival.
RESULTS:
ALPPS for PHC was associated with 48% (14/29) 90-day mortality. 90-day mortality was 13% in 257 patients who underwent major liver resection for PHC without ALPPS. The 29 ALPPS patients were matched to 29 patients resected without ALPPS, with similar future liver remnant volume (P = 0.480). Mortality in the matched control group was 24% (P = 0.100) and median OS was 27 months, comparted to 6 months after ALPPS (P = 0.064).
DISCUSSION:
Outcomes of ALPPS for PHC appear inferior compared to standard extended resections in high-risk patients. Therefore, portal vein embolization should remain the preferred method to increase future remnant liver volume in patients with PHC. ALPPS is not recommended for PHC
Detection of airborne Campylobacter with three bioaerosol samplers for alarming bacteria transmission in broilers.
No full textIn an airborne transmission experiment, Campylobacter in the air was sampled by three types of bioaerosol samplers (all-glass impinger AGI-30, Andersen six-stage impactor, and OMNI-3000) in four broiler rooms. In each room, five 14-day- old broilers inoculated with Campylobacter jejuni were kept in a central cage located in the middle of the room. Another ten broilers, as susceptible animals, were kept individually in ten cages surrounding the central cage at a distance of approximately 75 cm. Air samples were taken on eight days: the day before inoculation (BI) as a negative control, and 1, 3, 6, 9, 14, 21, and 29 days post-inoculation (PI). Presence of C. jejuni was investigated with the culture method for culturable bacteria and with the PCR test for bacterial DNA. Results showed that Campylobacter infection of susceptible broilers occurred in all four rooms; however, no culturable C. jejuni could be detected in any of the air samples. This might have been the result of the low number of broilers in the room and the unfavorable conditions for Campylobacter survival, leading to Campylobacter concentrations below the detection limits of the bioaerosol samplers. The PCR test showed that DNA of C. jejuni was detected in the air samples on the first day PI, but no bacterial DNA was detected on the following days. It is concluded that the three samplers used in this study are not able to alarm Campylobacter outbreaks through an airborne route when low bacterial concentrations are present. Developments of new sampling techniques with low detection limits are required for biosecurity assessment
Analysis Of Factors Affecting Ammonia And Methane Emissions From Pig Slurries: Slurry Composition And Dietary Factors
No full textReducing crude protein is a recommended technique to reduce nitrogen excretion and ammonia emissions. Greenhouse gas emissions from slurry are also affected by nutrient composition. However, there are interactions among nutrients in feeds still not clarified. The objective of this study was to evaluate the impacts of different diets on nitrogen (N) and energy balances. A total of 13 diets were evaluated in digestibility trials using 78 animals.
Diets were formulated to fulfil commercial standards, although differing in ingredient composition. Nutrient
intake, excretion and potential NH3 and CH4 (Biochemical methane potential) emissions from slurry were
measured. Animal weight was also monitored. Correlations between emissions and nutrient balance components were done. An analysis of variance was conducted to assess differences in nutrient balance of low, medium and high emitting animals, expressing animals per kg of live weight increased. For the N balance, a two-fold range in faeces to urine N excretion ratio was found throughout the experiments, even considering the low crude protein variations (from 15 to 16%). This was related to the ammonia emissions from slurry (r = -0.60, p<0.001). In fact, the amount of crude protein ingested to increase 1 kg of metabolic weight was positively correlated with the associated emissions (r=0.58, p<0.001). However, this was more related to the consumption by the animal than to the crude protein, which was relatively stable among diets. The difference between animals associated with high or low NH3 emissions per weight gain was therefore related to urine losses due to excess N intake. The energy balance shows that methane potential from slurry was mainly related to the excretion of indigested feed components, mainly the fibrous fraction (particularly the soluble fibre). It was clear that animals emitting high amounts of methane were those with higher dry matter and energy ingestion. The results of this study demonstrate relevant effects on N and energy balances at diets formulated according to commercial standards
Effect of type of aviary, manure and litter handling on the emission kinetics of ammonia from layer houses
No full textU-Index: A Universal Indexing Framework for Matching Long Patterns
No full textMotivation. 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
Tailored care in resectable perihilar cholangiocarcinoma
No full textSurgical resection of perihilar cholangiocarcinoma offers a distinct benefit in long-term survival, but it is a complex procedure. The tumour may extend into segmental branches of the bile ducts, or involve the portal vein and/or hepatic artery. Curative-intent resection requires a combined extrahepatic bile duct and partial liver resection, sometimes including a portal vein resection and reconstruction. These extended procedures are associated with a high risk of postoperative mortality, even more so because many patients present with obstructive jaundice. Selecting the optimal treatment in patients with perihilar cholangiocarcinoma is a trade-off between opportunities for long-term survival against the danger of procedural risks: surgery offers a chance for long-term survival or cure, but perioperative complications may cause abrupt death. This thesis aimed to provide recommendations and clinical decision rules for tailored care in patients with resectable perihilar cholangiocarcinoma
De ammoniakemissie uit drie typen volierestallen voor leghennen
No full textDoel van het onderzoek was om de hoogte van de ammoniakemissie uit 3 volièrestalsystemen (het Etage-, het Natura- en het Righs Bolegsysteem) vast te stellen en na te gaan of de emissieverschillen verklaard kunnen worden uit de inrichtingsverschillen tussen de stallen, de mest en het strooisel. Het strooiseloppervlak en het aantal en de plaatsing van de etages verschilde per systeem. Onder alle etages was een mestband aanwezig, die 2x per week werd afgedraaid
- …
