8 research outputs found
A comparison of growth responses between two species of Potamogeton with contrasting canopy architecture
No full textCopyright © 2001 Elsevier Science B.V. All rights reserved.David Cenzato and George Ganfhttp://www.elsevier.com/wps/find/journaldescription.cws_home/503303/description#descriptio
Processing and indexing large biological datasets using the Burrows-Wheeler Transform of string collections
No full textIn the last few decades, the advent of next-generation sequencing technologies (NGS) has dramatically reduced the cost of DNA sequencing. This has made it possible to sequence many genomes in very little time, paving the way for projects which aim at the creation of large and repetitive collections of genomic sequences. The abundance of biological data is driving the development of new memory-efficient algorithms and data structures that can scale for large datasets, thus tackling the high computational burden related to processing these data. This trend has a strong impact on the text algorithms area. In this thesis, we will study the Burrows-Wheeler Transform for processing, indexing, and compressing collections of strings. Data compression addresses the problem of encoding the input to reduce the space needed for storing it, while text indexing focuses on finding ways to efficiently process and extract information from the data. In bioinformatics, these two concepts have been frequently used together since they allow the design of data structures that can efficiently process biological data while keeping the input compressed. The Burrows-Wheeler Transform (BWT) is a reversible transformation on strings introduced by Michael Burrows and David J. Wheeler in 1994 that plays a central role in this area. It is the key component of several compressed data structures for text processing, like the FM-index [Ferraggina and Manzini, SODA, 2000] or the r-index [Gagie et al., SODA, 2018], and some of the most important software in bioinformatics, such as the well-known Bowtie [Langmead et al., Genome Biology, 2009] and BWA [Li and Durbin, Bioinformatics, 2010]. The BWT was originally defined for individual strings, so when the focus moved from single sequences to string collections, there was the need to extend this transform. Over the years, several different tools and algorithms for computing BWT of string collections were introduced. However, even if the transforms generated by these tools frequently differ from each other, the problem of characterizing the BWT variants was never addressed properly. In this thesis, we close this gap by presenting the first systematic study of the BWT of string collections. We identified five non-equivalent variants computed by the tools in current use and analyzed their properties to show how exactly they differ. We complete our theoretical analysis by comparing the five BWT variants on several real-life biological datasets. We show that not only the differences among the resulting transforms can be extensive, but they also lead to significant changes in the compressibility of the BWT of the underlying string collection. As a further complication, the BWT variants in use often depend on the input order of the sequences. This significantly impacts the number of runs r, which defines the size of BWT-based compressed data structures. In this thesis, we address the problem of reordering the input sequences by providing the first implementation of the algorithm of Bentley et al. [ESA 2020], which computes the order minimizing the number of runs of the BWT. This leads to the creation of the first tool for computing the optimal BWT, i.e., the BWT variant which guarantees the minimum number of runs. We show experimentally that the input order can dramatically affect the final result: on our real-life datasets, the optimal BWT had up to 31 times fewer runs than the BWT computed without reordering the input sequences. The extended BWT (eBWT) of Mantaci et al. [Theor. Comput. Sci. 2007] is one of the first BWT variants explicitly designed to process string collections. Even though this transform is mathematically sound and has useful properties, its construction has been a problem for more than a decade. In this thesis, we present two linear-time algorithms for computing the eBWT of large string collections. The first is an improvement of the Bijective BWT construction algorithm of Bannai et al. [CPM 2019], while the second uses the Prefix-free parsing (PFP) method [Boucher et al., Algorithms Mol. Biol., 2019] to specifically process large and repetitive genomic sequence collections. In the final part of the thesis, we conclude by studying, for the first time, how to index string collections using the eBWT. We present the extended r-index, an extension of the r-index to the eBWT, which maintains the same performance as the original r-index while inheriting the properties of the eBWT. We implemented this data structure using a variant of the PFP algorithm and tested it on real-life biological datasets containing circular bacterial genomes and plasmids. We show experimentally that our index has competitive query times compared to the r-index on different pattern lengths while supporting advanced pattern matching functionalities on circular sequences
The pulmonary surfactant system matures upon pipping in the freshwater turtle Chelydra serpentina
No full text© The Company of BiologistsPulmonary surfactant (PS), a mixture of phospholipids (PL), neutral lipids and surfactant proteins (SP), lowers surface tension within the lung, which increases lung compliance and improves the removal of fluid at birth. Here, we have examined the expression of thyroid transcription factor-1 (TTF-1) and the surfactant protein SP-B, and also the composition of pulmonary surfactant lipids in the developing lung of the turtle Chelydra serpentina. Lavage and lung tissue were collected from late embryonic, pipped and hatchling turtles. TTF-1, a regulator of gene expression of surfactant proteins and cell differentiation in mammals, was detected using immunohistochemistry in epithelia of the gas-exchange area and conducting airways during late development. Expression declined in hatchlings. SP-B was detected in subsets of cells within the respiratory epithelium at all stages sampled. The same cell types also stained for TTF-1. Turtle surfactant lipids matured toward the end of incubation. Maximal secretion of both total phospholipids and disaturated phospholipid (DSP) occurred at the time of pipping, coincident with the onset of breathing. The DSP/PL ratio increased after pipping, whereas cholesterol levels (Chol) increased prior to pipping. This resulted in a decrease in the Chol/PL and Chol/DSP ratios after pipping. Thus, TTF-1 and SP-B appear to be highly conserved within the vertebrates. Maturation of surfactant phospholipid content occurred with the commencement of pulmonary ventilation.Sonya D. Johnston, Christopher B. Daniels, David Cenzato, Jeffrey A. Whitsett and Sandra Orgei
On the Number of Equal-Letter Runs of the Bijective Burrows-Wheeler Transform
No full textThe Bijective Burrows-Wheeler Transform (BBWT) is a variant of the famous BWT [Burrows and Wheeler, 1994]. The BBWT was introduced by Gil and Scott in 2012, and is based on the extended BWT of Mantaci et al. [TCS 2007] and on the Lyndon factorization of the input string. In the original paper, the compression achieved with the BBWT was shown to be competitive with that of the BWT, and it has been gaining interest in recent years. In this work, we present the first study of the number of runs rB of the BBWT, which is a measure of its compression power. We exhibit an infinite family of strings on which rB of the string and of its reverse differ by a multiplicative factor of T(log n), where n is the length of the string.Peer reviewe
Mezzogiorno e fascismo
No full textThe relationship between Southern Italy and fascism is a little explored theme. The contribution reflects on this subject presenting unpublished conclusions: it starts from a volume by the author named after the monthly magazine 'Il Saggiatore' (Naples 1924-1925) by Gherardo Marone and expands the reflection through a more recent book by Zoppi dedicated to the magazine 'Questioni meridionali', also published in Naples, from 1934 to 1943. The three editors of 'Questioni meridionali' - Giuseppe Cenzato, an entrepreneur who was also the soul of the company, Francesco Giordani, a young chemical scientist, and Gino Olivetti, a politician and industrialist – despite being fascists, they created a periodical that showed how the 'Southern question', never mentioned by the dictatorship, remained, however, alive in its tragic backwardness. Every year, two large issues of the magazine were released, characterized by one or more original studies and always accompanied by extensive bibliographic reviews. Among the topics, analysed by a group of highly qualified scholars and often in comparison with the North of Italy, the following emerged: the railway network, tourism, the demographic and health situation, the birth rate, the difficulties of the construction industry, ports, the economic and production context. The magazine pays particular attention to the city of Naples and its housing drama and to the southern tax system, a primary source of backwardness starting with the problem of local government
Chapter Mezzogiorno e fascismo
No full textThe relationship between Southern Italy and fascism is a little explored theme. The contribution reflects on this subject presenting unpublished conclusions: it starts from a volume by the author named after the monthly magazine 'Il Saggiatore' (Naples 1924-1925) by Gherardo Marone and expands the reflection through a more recent book by Zoppi dedicated to the magazine 'Questioni meridionali', also published in Naples, from 1934 to 1943. The three editors of 'Questioni meridionali' - Giuseppe Cenzato, an entrepreneur who was also the soul of the company, Francesco Giordani, a young chemical scientist, and Gino Olivetti, a politician and industrialist – despite being fascists, they created a periodical that showed how the 'Southern question', never mentioned by the dictatorship, remained, however, alive in its tragic backwardness. Every year, two large issues of the magazine were released, characterized by one or more original studies and always accompanied by extensive bibliographic reviews. Among the topics, analysed by a group of highly qualified scholars and often in comparison with the North of Italy, the following emerged: the railway network, tourism, the demographic and health situation, the birth rate, the difficulties of the construction industry, ports, the economic and production context. The magazine pays particular attention to the city of Naples and its housing drama and to the southern tax system, a primary source of backwardness starting with the problem of local government
Preface to “Computation over Compressed Data” at DCC 2022
No full textThis is the fifth special issue of the “computation over compressed data” session at the IEEE Data Compression Conference (DCC), which took place in Snowbird on March 22-24, 2022. This special issue features six articles from the field of compressed data structures, covering compact graph data structures and efficient algorithms and indexes for several variants of the ubiquitous Burrows-Wheeler transform.
In “Compact representations of spatial hierarchical structures with support for topological queries”, José Fuentes-Sepúlveda, Diego Gatica, Gonzalo Navarro, M. Andrea Rodríguez, and Diego Seco show how to compactly represent hierarchical bidimensional spatial regions (such as the administrative partition of a country) while supporting a number of useful queries on the data. Their representation builds upon compact planar graph embeddings. New compact data structures for graphs are presented also in “Succinct data structure for path graphs”. Here, the authors Girish Balakrishnan, Sankardeep Chakraborty, N.S. Narayanaswamy and Kunihiko Sadakane show how to support efficient degree, adjacency, and neighborhood queries on path graphs in a space matching the information-theoretic lower bound.
The remaining four papers deal with variants of the Burrows-Wheeler transform (BWT), a fundamental tool in text compression and indexing whose introduction in 1994 by Michael Burrows and David J. Wheeler opened a prolific line of research in the fields of data compression and indexing. In “A new class of string transformations for compressed text indexing”, Raffaele Giancarlo, Giovanni Manzini, Antonio Restivo, Giovanna Rosone, and Marinella Sciortino generalize the BWT by using context-adaptive alphabet orderings. They show that, under certain conditions, on very repetitive text collections these more general transformations are indexable and more compressible than the original BWT. While the problem of building the BWT in linear time and space is well-understood to date, such repetitive collections pose the challenge of solving this task in compressed space: in those cases, the input is too large to be kept in memory in uncompressed format. This problem is tackled by Diego Díaz-Domínguez and Gonzalo Navarro in “Efficient construction of the BWT for repetitive text using string compression”. In this article, the authors show how to build a BWT variant (BCR BWT) with an algorithm keeping its intermediate results in grammar-compressed form. The resulting algorithm spectacularly achieves its goal, using a working space not exceeding 10% of the input’s size on real repetitive datasets. In “Constructing and indexing the bijective and extended Burrows–Wheeler transform”, Hideo Bannai, Juha Kärkkäinen, Dominik Köppl, and Marcin Pia̧tkowski consider the problem of building another BWT variant: the bijective BWT. They describe the first linear-time construction algorithm for such a variant, and present the first self-index based on the bijective BWT. Last but not least, in “r-indexing the eBWT” the authors Christina Boucher, Davide Cenzato, Zsuzsanna Lipták, Massimiliano Rossi, and Marinella Sciortino show how to index yet another BWT variant: the eBWT, originally designed to compactly represent collections of circular strings. They describe an extension of the r-index for such collections, able to simultaneously achieve high compression rates on very repetitive data, and (for the first time) to index circular strings.
The success of this special issue shows that the field of compressed data structures is still very active and flourishing. As a matter of fact, these six articles clearly indicate two of the directions that the community is taking: compressing and indexing graphs and very repetitive text collections. In March 2024 a new special session on “computation over compressed data” took place at DCC, featuring ten new articles in the field which may result in a new successful special issue
Casemix, management, and mortality of patients receiving emergency neurosurgery for traumatic brain injury in the Global Neurotrauma Outcomes Study: a prospective observational cohort study
No full textBackground: Traumatic brain injury (TBI) is increasingly recognised as being responsible for a substantial proportion of the global burden of disease. Neurosurgical interventions are an important aspect of care for patients with TBI, but there is little epidemiological data available on this patient population. We aimed to characterise differences in casemix, management, and mortality of patients receiving emergency neurosurgery for TBI across different levels of human development. Methods: We did a prospective observational cohort study of consecutive patients with TBI undergoing emergency neurosurgery, in a convenience sample of hospitals identified by open invitation, through international and regional scientific societies and meetings, individual contacts, and social media. Patients receiving emergency neurosurgery for TBI in each hospital's 30-day study period were all eligible for inclusion, with the exception of patients undergoing insertion of an intracranial pressure monitor only, ventriculostomy placement only, or a procedure for drainage of a chronic subdural haematoma. The primary outcome was mortality at 14 days postoperatively (or last point of observation if the patient was discharged before this time point). Countries were stratified according to their Human Development Index (HDI)—a composite of life expectancy, education, and income measures—into very high HDI, high HDI, medium HDI, and low HDI tiers. Mixed effects logistic regression was used to examine the effect of HDI on mortality while accounting for and quantifying between-hospital and between-country variation. Findings: Our study included 1635 records from 159 hospitals in 57 countries, collected between Nov 1, 2018, and Jan 31, 2020. 328 (20%) records were from countries in the very high HDI tier, 539 (33%) from countries in the high HDI tier, 614 (38%) from countries in the medium HDI tier, and 154 (9%) from countries in the low HDI tier. The median age was 35 years (IQR 24–51), with the oldest patients in the very high HDI tier (median 54 years, IQR 34–69) and the youngest in the low HDI tier (median 28 years, IQR 20–38). The most common procedures were elevation of a depressed skull fracture in the low HDI tier (69 [45%]), evacuation of a supratentorial extradural haematoma in the medium HDI tier (189 [31%]) and high HDI tier (173 [32%]), and evacuation of a supratentorial acute subdural haematoma in the very high HDI tier (155 [47%]). Median time from injury to surgery was 13 h (IQR 6–32). Overall mortality was 18% (299 of 1635). After adjustment for casemix, the odds of mortality were greater in the medium HDI tier (odds ratio [OR] 2·84, 95% CI 1·55–5·2) and high HDI tier (2·26, 1·23–4·15), but not the low HDI tier (1·66, 0·61–4·46), relative to the very high HDI tier. There was significant between-hospital variation in mortality (median OR 2·04, 95% CI 1·17–2·49). Interpretation: Patients receiving emergency neurosurgery for TBI differed considerably in their admission characteristics and management across human development settings. Level of human development was associated with mortality. Substantial opportunities to improve care globally were identified, including reducing delays to surgery. Between-hospital variation in mortality suggests changes at an institutional level could influence outcome and comparative effectiveness research could identify best practices. Funding: National Institute for Health Research Global Health Research Group
