Search

Background: Global access to acute stroke treatment is variable worldwide, with notable gaps in low and middle-income countries (LMIC), especially in rural areas. Ensuring a standardized method for pinpointing the existing regional coverage and proposing potential sites for new stroke centers is essential to change this scenario. Aims: To create and apply computational strategies (CSs) to determine optimal locations for new acute stroke centers (ASCs), with a pilot application in nine Latin American regions/countries. Methods: Hospitals treating acute ischemic stroke (AIS) with intravenous thrombolysis (IVT) and meeting the minimum infrastructure requirements per structured protocols were categorized as ASCs. Hospitals with emergency departments, noncontrast computed tomography (NCCT) scanners, and 24/7 laboratories were identified as potential acute stroke centers (PASCs). Hospital geolocation data were collected and mapped using the OpenStreetMap data set. A 45-min drive radius was considered the ideal coverage area for each hospital based on the drive speeds from the OpenRouteService database. Population data, including demographic density, were obtained from the Kontur Population data sets. The proposed CS assessed the population covered by ASCs and proposed new ASCs or artificial points (APs) settled in densely populated areas to achieve a target population coverage (TPC) of 95%. Results: The observed coverage in the region presented significant disparities, ranging from 0% in the Bahamas to 73.92% in Trinidad and Tobago. No country/region reached the 95% TPC using only its current ASCs or PASCs, leading to the proposal of APs. For example, in Rio Grande do Sul, Brazil, the introduction of 132 new centers was suggested. Furthermore, it was observed that most ASCs were in major urban hubs or university hospitals, leaving rural areas largely underserved. Conclusions: The MAPSTROKE project has the potential to provide a systematic approach to identify areas with limited access to stroke centers and propose solutions for increasing access to AIS treatment. Data access statement: Data used for this publication are available from the authors upon reasonable request. [ABSTRACT FROM AUTHOR]

Genome assembly asks to reconstruct an unknown string from many shorter substrings of it. Even though it is one of the key problems in Bioinformatics, it is generally lacking major theoretical advances. Its hardness stems both from practical issues (size and errors of real data), and from the fact that problem formulations inherently admit multiple solutions. Given these, at their core, most state-of-the-art assemblers are based on finding non-branching paths (unitigs) in an assembly graph. While such paths constitute only partial assemblies, they are likely to be correct. More precisely, if one defines a genome assembly solution as a closed arc-covering walk of the graph, then unitigs appear in all solutions, being thus safe partial solutions. Until recently, it was open what are all the safe walks of an assembly graph. Tomescu and Medvedev (RECOMB 2016) characterized all such safe walks (omnitigs), thus giving the first safe and complete genome assembly algorithm. Even though maximal omnitig finding was later improved to quadratic time by Cairo et al. (ACM Trans. Algorithms 2019), it remained open whether the crucial linear-time feature of finding unitigs can be attained with omnitigs. We answer this question affirmatively, by describing a surprising O(m)-time algorithm to identify all maximal omnitigs of a graph with n nodes and m arcs, notwithstanding the existence of families of graphs with Θ (mn) total maximal omnitig size. This is based on the discovery of a family of walks (macrotigs) with the property that all the non-trivial omnitigs are univocal extensions of subwalks of a macrotig. This has two consequences: (1) A linear-time output-sensitive algorithm enumerating all maximal omnitigs. (2) A compact O(m) representation of all maximal omnitigs, which allows, e.g., for O(m)-time computation of various statistics on them. Our results close a long-standing theoretical question inspired by practical genome assemblers, originating with the use of unitigs in 1995. We envision our results to be at the core of a reverse transfer from theory to practical and complete genome assembly programs, as has been the case for other key Bioinformatics problems. [ABSTRACT FROM AUTHOR]

Given a string S of length n, the classic string indexing problem is to preprocess S into a compact data structure that supports efficient subsequent pattern queries. In this article, we consider the basic variant where the pattern is given in compressed form and the goal is to achieve query time that is fast in terms of the compressed size of the pattern. This captures the common client-server scenario, where a client submits a query and communicates it in compressed form to a server. Instead of the server decompressing the query before processing it, we consider how to efficiently process the compressed query directly. Our main result is a novel linear space data structure that achieves near-optimal query time for patterns compressed with the classic Lempel-Ziv 1977 (LZ77) compression scheme. Along the way, we develop several data structural techniques of independent interest, including a novel data structure that compactly encodes all LZ77 compressed suffixes of a string in linear space and a general decomposition of tries that reduces the search time from logarithmic in the size of the trie to logarithmic in the length of the pattern. [ABSTRACT FROM AUTHOR]

Homologous recombination between the maternal and paternal copies of a chromosome is a key mechanism for human inheritance and shapes population genetic properties of our species. However, a similar mechanism can also act between different copies of the same sequence, then called non-allelic homologous recombination (NAHR). This process can result in genomic rearrangements—including deletion, duplication, and inversion—and is underlying many genomic disorders. Despite its importance for genome evolution and disease, there is a lack of computational models to study genomic loci prone to NAHR. In this work, we propose such a computational model, providing a unified framework for both (allelic) homologous recombination and NAHR. Our model represents a set of genomes as a graph, where haplotypes correspond to walks through this graph. We formulate two founder set problems under our recombination model, provide flow-based algorithms for their solution, describe exact methods to characterize the number of recombinations, and demonstrate scalability to problem instances arising in practice. [ABSTRACT FROM AUTHOR]

Optical character recognition (OCR) is one of the most popular techniques used for converting printed documents into machine-readable ones. While OCR engines can do well with modern text, their performance is unfortunately significantly reduced on historical materials. Additionally, many texts have already been processed by various out-of-date digitisation techniques. As a consequence, digitised texts are noisy and need to be post-corrected. This article clarifies the importance of enhancing quality of OCR results by studying their effects on information retrieval and natural language processing applications. We then define the post-OCR processing problem, illustrate its typical pipeline, and review the state-of-the-art post-OCR processing approaches. Evaluation metrics, accessible datasets, language resources, and useful toolkits are also reported. Furthermore, the work identifies the current trend and outlines some research directions of this field. [ABSTRACT FROM AUTHOR]

Computing the similarity of two point sets is a ubiquitous task in medical imaging, geometric shape comparison, trajectory analysis, and many more settings. Arguably the most basic distance measure for this task is the Hausdorff distance, which assigns to each point from one set the closest point in the other set and then evaluates the maximum distance of any assigned pair. A drawback is that this distance measure is not translational invariant, that is, comparing two objects just according to their shape while disregarding their position in space is impossible. Fortunately, there is a canonical translational invariant version, the Hausdorff distance under translation, which minimizes the Hausdorff distance over all translations of one of the point sets. For point sets of size n and m, the Hausdorff distance under translation can be computed in time Õ(nm) for the L1 and L∞ norm [Chew, Kedem SWAT'92] and Õ(nm(n + m)) for the L2 norm [Huttenlocher, Kedem, Sharir DCG'93]. As these bounds have not been improved for over 25 years, in this paper we approach the Hausdorff distance under translation from the perspective of fine-grained complexity theory. We show (i) a matching lower bound of (nm)1-o(1) for L1 and L∞ (and all other Lp norms) assuming the Orthogonal Vectors Hypothesis and (ii) a matching lower bound of n2-o(1) for L2 in the imbalanced case of m = O(1) assuming the 3SUM Hypothesis. [ABSTRACT FROM AUTHOR]