Search

Background: While emergency medicine (ER)-based emergency care is prevalent in many countries, in Japan, the "department-specific emergency care model" and the "emergency center model" are mainstream. We hypothesized that many secondary emergency medical institutions in Japan have inadequate systems. Using a questionnaire, we investigated the status of and problems in the emergency medical services system in secondary emergency medical institutions in Japan. Until date, there has not been an exhaustive survey of emergency facilities on a countrywide scale. The main objective of this study was to investigate problems in the Japanese emergency medical services system and thereby improve optimal care for emergency patients. Results: A nationwide questionnaire survey involving 4063 facilities (all government-approved emergency medical facilities certified by prefectural governors) in Japan was conducted. Of the facilities that responded, all secondary emergency facilities were included in the analysis. Responses from 1289 facilities without a tertiary emergency medical care center were analyzed. Among them, 61% (792/1289) had ≤ 199 beds, and 8% were emergency department specialty training program core facilities. Moreover, 42% had an annual patient acceptance number of ≤ 500, 19% did not calculate the number of acceptances, 29% had an acceptance rate of ≥ 81%, and 25% had an acceptance rate of 61–80%. Pregnant women (63%) and children (56%) were the major types of patients that affected the acceptance rate. Factors affecting facilities with a response rate of 81% or higher were "hospitals designated for residency training" and "facilities making some efforts to improve the quality of emergency care and the emergency medical system" (logistic analysis, P <.001). Conclusion: Relevant authorities and core regional facilities should consider and implement specific measures for regions and hospitals with a shortage of emergency medicine specialists and physicians (e.g., development of ER-based emergency medicine and provision of education). This study may lead to further improvement in the optimal care of emergency patients through the nationwide establishment of the proposed measures as well as through grouping and integrating the structures and systems in emergency and other medical facilities. [ABSTRACT FROM AUTHOR]

We have identified cDNA encoding a new member of the adrenomedullin (AM) family, AM2, for the first time in mammals (mouse, rat and human). The predicted precursor carried mature AM2 in the C-terminus, which had an intramolecular ring formed by an S–S bond and a possibly amidated C-terminus. Phylogenetic analyses clustered AM2 and AM into two distinct but closely related groups. Similarity of exon–intron structure and synteny of neighboring genes showed that mammalian AM2 is an ortholog of pufferfish AM2 and a paralog of mammalian AM. AM2 mRNA was expressed in submaxillary gland, kidney, stomach, ovary, lymphoid tissues and pancreas of mice, but not in adrenal and testis. Intravenous injection of synthetic mature AM2 decreased arterial pressure more potently than AM, and induced antidiuresis and antinatriuresis in mice. These results show that at least two peptides, AM and AM2, comprise an adrenomedullin family in mammals, and that AM2 may play pivotal roles in cardiovascular and body fluid regulation. [Copyright &y& Elsevier]

FM-indexes are crucial data structures in DNA alignment, but searching with them usually takes at least one random access per character in the query pattern. Ferragina and Fischer [1] observed in 2007 that word-based indexes often use fewer random accesses than character-based indexes, and thus support faster searches. Since DNA lacks natural word-boundaries, however, it is necessary to parse it somehow before applying word-based FM-indexing. In 2022, Deng et al. [2] proposed parsing genomic data by induced suffix sorting, and showed that the resulting word-based FM-indexes support faster counting queries than standard FM-indexes when patterns are a few thousand characters or longer. In this paper we show that using prefix-free parsing—which takes parameters that let us tune the average length of the phrases—instead of induced suffix sorting, gives a significant speedup for patterns of only a few hundred characters. We implement our method and demonstrate it is between 3 and 18 times faster than competing methods on queries to GRCh38, and is consistently faster on queries made to 25,000, 50,000 and 100,000 SARS-CoV-2 genomes. Hence, it seems our method accelerates the performance of count over all state-of-the-art methods with a moderate increase in the memory. The source code for PFP - FM is available at https://github.com/AaronHong1024/afm. [ABSTRACT FROM AUTHOR]

Two strings x and y over Σ ∪ Π of equal length are said to parameterized match (p-match) if there is a renaming bijection f : Σ ∪ Π → Σ ∪ Π that is identity on Σ and transforms x to y (or vice versa). The p-matching problem is to look for substrings in a text that p-match a given pattern. In this paper, we propose parameterized suffix automata (p-suffix automata) and parameterized directed acyclic word graphs (PDAWGs) which are the p-matching versions of suffix automata and DAWGs. While suffix automata and DAWGs are equivalent for standard strings, we show that p-suffix automata can have Θ (n 2) nodes and edges but PDAWGs have only O (n) nodes and edges, where n is the length of an input string. We also give an O (n | Π | log ⁡ (| Π | + | Σ |)) -time O (n) -space algorithm that builds the PDAWG in a left-to-right online manner. As a byproduct, it is shown that the parameterized suffix tree for the reversed string can also be built in the same time and space, in a right-to-left online manner. This duality also leads us to two further efficient algorithms for p-matching: Given the parameterized suffix tree for the reversal T ‾ of the input string T , one can build the PDAWG of T in O (n) time in an offline manner; One can perform bidirectional p-matching in O (m log ⁡ (| Π | + | Σ |) + occ) time using O (n) space, where m denotes the pattern length and occ is the number of pattern occurrences in the text T. [ABSTRACT FROM AUTHOR]

One of the most fundamental method for comparing two given strings A and B is the longest common subsequence (LCS), where the task is to find (the length) of an LCS of A and B. In this paper, we deal with the STR-IC-LCS 1 problem which is one of the constrained LCS problems proposed by Chen and Chao [J. Comb. Optim, 2011]. A string Z is said to be an STR-IC-LCS of three given strings A , B , and P , if Z is a longest string satisfying that (1) Z includes P as a substring and (2) Z is a common subsequence of A and B. We present three efficient algorithms for this problem: First, we begin with a space-efficient solution which computes the length of an STR-IC-LCS in O (n 2) time and O ((ℓ + 1) (n − ℓ + 1)) space, where ℓ is the length of an LCS of A and B of length n. When ℓ = O (1) or n − ℓ = O (1) , then this algorithm uses only linear O (n) space. Second, we present a faster algorithm that works in O (n r / log ⁡ r + n (n − ℓ + 1)) time, where r is the length of P , while retaining the O ((ℓ + 1) (n − ℓ + 1)) space efficiency. Third, we give an alternative algorithm that runs in O (n r / log ⁡ r + n (n − ℓ ′ + 1)) time with O ((ℓ ′ + 1) (n − ℓ ′ + 1)) space, where ℓ ′ denotes the STR-IC-LCS length for input strings A , B , and P. [ABSTRACT FROM AUTHOR]

A string w is called a minimal absent word (MAW) for another string T if w does not occur in T but the proper substrings of w occur in T. For example, let Σ = { a , b , c } be the alphabet. Then, the set of MAWs for string w = abaab is { aaa , aaba , bab , bb , c }. In this paper, we study combinatorial properties of MAWs in the sliding window model, namely, how the set of MAWs changes when a sliding window of fixed length d is shifted over the input string T of length n , where 1 ≤ d < n. We present tight upper and lower bounds on the maximum number of changes in the set of MAWs for a sliding window over T , both in the cases of general alphabets and binary alphabets. Our bounds improve on the previously known best bounds [Crochemore et al., 2020]. [ABSTRACT FROM AUTHOR]

A factorization f1,...,fm of a string w is called a repetition factorization of w if each factor fi is a repetition, namely, f i = x k x ′ for some non-empty string x, an integer k ≥ 2, and x ′ being a proper prefix of x. Dumitran et al. (Proc. SPIRE 2015) proposed an algorithm which computes an arbitrary repetition factorization of a given string w in O(n) time, where n is the length of w. The number of factors (i.e. repetitions) contained in the output of their algorithm is not known or guaranteed. In this paper, we propose two algorithms for computing smallest/largest repetition factorizations in O (n log n) time, which respectively consist of the smallest/largest number of factors. The first algorithm is a simple O (n log n) -space algorithm based on a reduction of the problem to the shortest/longest path problem on the DAG of size O (n log n) . The second one simulates the dynamic programming algorithm for shortest/longest path problem within O(n) space based on the idea of the first algorithm. Moreover, we discuss combinatorial structures of smallest/largest repetition factorizations of Fibonacci strings. [ABSTRACT FROM AUTHOR]

A substring u of a string T is called a minimal unique substring (MUS) of T if u occurs exactly once in T and any proper substring of u occurs at least twice in T. In this paper, we study the problem of computing MUSs for a sliding window over a given string T. We first show how the set of MUSs can change when the window slides over T. We then present an O (n log σ ′) -time and O(d)-space algorithm to compute MUSs for a sliding window of size d over the input string T of length n, where σ ′ ≤ d is the maximum number of distinct characters in every window. [ABSTRACT FROM AUTHOR]

Abstract: A suffix tree, which provides us with a linear space full-text index of a given string, is a fundamental data structure for string processing and information retrieval. In this paper we consider the reverse engineering problem on suffix trees: given an unlabeled ordered rooted tree accompanied with a node-to-node transition function , infer a string whose suffix tree and its suffix links for inner nodes are isomorphic to and , respectively. Also, we consider the enumeration problem in which we enumerate all strings corresponding to an input tree and links. By introducing new characterizations of suffix trees, we show that the reverse engineering problem and the enumeration problem on suffix trees on a binary alphabet can be solved in optimal time. [Copyright &y& Elsevier]

In this paper, we propose a new dynamic compressed index of O (w) space for a dynamic text T , where w = O (min (z log N log ∗ M , N)) is the size of the signature encoding of T , z is the size of the Lempel–Ziv77 (LZ77) factorization of T , N is the length of T , and M ≥ N is the maximum length of T. Our index supports searching for a pattern P in T in O (| P | f A + log w log | P | log ∗ M (log N + log | P | log ∗ M) + occ log N) time and insertion/deletion of a substring of length y in O ((y + log N log ∗ M) log w log N log ∗ M) time, where occ is the number of occurrences of P in T and f A = O (min { log log M log log w log log log M , log w log log w }). Also, we propose a new space-efficient LZ77 factorization algorithm for a given text T , which runs in O (N f A + z log w log 3 N (log ∗ N) 2) time with O (w) working space. [ABSTRACT FROM AUTHOR]

The directed acyclic word graph (DAWG) of a string y of length n is the smallest (partial) DFA which recognizes all suffixes of y with only O (n) nodes and edges. In this paper, we show how to construct the DAWG for the input string y from the suffix tree for y , in O (n) time for integer alphabets of polynomial size in n. In so doing, we first describe a folklore algorithm which, given the suffix tree for y , constructs the DAWG for the reversed string y ˆ in O (n) time. Then, we present our algorithm that builds the DAWG for y in O (n) time for integer alphabets, from the suffix tree for y. We also show that a straightforward modification to our DAWG construction algorithm leads to the first O (n) -time algorithm for constructing the affix tree of a given string y over an integer alphabet. Affix trees are a text indexing structure supporting bidirectional pattern searches. We then discuss how our constructions can lead to linear-time algorithms for building other text indexing structures, such as linear-size suffix tries and symmetric CDAWGs in linear time in the case of integer alphabets. As a further application to our O (n) -time DAWG construction algorithm, we show that the set MAW (y) of all minimal absent words (MAWs) of y can be computed in optimal , input- and output-sensitive O (n + | MAW (y) |) time and O (n) working space for integer alphabets. [ABSTRACT FROM AUTHOR]

Given a pattern p of size m and a text t , the problem of order-preserving pattern matching (OPPM) is to find all substrings of t that satisfy one of the orderings defined by p. This problem has applications on time series analysis. However given its strict nature this model is unable to deal with indetermination, thus limiting its application to noisy time series. In this paper we introduce indeterminate characters to alleviate this limitation. We then propose two polynomial time algorithms. If the indetermination is limited to p confirming one occurrence can be computed in O (r m lg ⁡ r) time, where r is a bound on the number of uncertain characters per position. If the indetermination alternates, but does not occur at the same position in t and p , we present an algorithm that requires O (r m (m + log ⁡ r)) time. We also show that the general problem is NP-hard and provide a polynomial size boolean formula. [ABSTRACT FROM AUTHOR]

Given a dynamic set K of k strings of total length n whose characters are drawn from an alphabet of size σ , a keyword dictionary is a data structure built on K that provides lookup, prefix search, and update operations on K. Under the assumption that α = w / lg ⁡ σ characters fit into a single machine word of w bits, we propose a keyword dictionary that represents K in either n lg ⁡ σ + Θ (k lg ⁡ n) or | T | lg ⁡ σ + Θ (k w) bits of space, where | T | is the number of nodes of a trie representing K. It supports all operations in O (m / α + lg ⁡ α) expected time on an input string of length m in the word RAM model. An evaluation of our implementation highlights the practical usefulness of the proposed data structure, especially for prefix searches — one of the most essential keyword dictionary operations. [ABSTRACT FROM AUTHOR]

Genomic regions under positive selection harbor variation linked for example to adaptation. Most tools for detecting positively selected variants have computational resource requirements rendering them impractical on population genomic datasets with hundreds of thousands of individuals or more. We have developed and implemented an efficient haplotype-based approach able to scan large datasets and accurately detect positive selection. We achieve this by combining a pattern matching approach based on the positional Burrows-Wheeler transform with model-based inference which only requires the evaluation of closed-form expressions. We evaluate our approach with simulations, and find it to be both sensitive and specific. The computational resource requirements quantified using UK Biobank data indicate that our implementation is scalable to population genomic datasets with millions of individuals. Our approach may serve as an algorithmic blueprint for the era of "big data" genomics: a combinatorial core coupled with statistical inference in closed form., (© The Author(s) 2023. Published by Oxford University Press on behalf of Society for Molecular Biology and Evolution.)

We consider the problem of finding the optimal combination of string patterns, which characterizes a given set of strings that have a numeric attribute value assigned to each string. Pattern combinations are scored based on the correlation between their occurrences in the strings and the numeric attribute values. The aim is to find the combination of patterns which is best with respect to an appropriate scoring function. We present an O(N2) time algorithm for finding the optimal pair of substring patterns combined with Boolean functions, where N is the total length of the sequences. The algorithm looks for all possible Boolean combinations of the patterns, e.g., patterns of the form p and not q, which indicates that the pattern pair is considered to occur in a given string s, if p occurs in s, AND q does NOT occur in s. An efficient implementation using suffix arrays is presented, and we further show that the algorithm can be adapted to find the best k-pattern Boolean combination in O(Nk) time. The algorithm is applied to mRNA sequence data sets of moderate size combined with their turnover rates for the purpose of finding regulatory elements that cooperate, complement, or compete with each other in enhancing and/or silencing mRNA decay.

We present a new approach to pattern discovery called string pattern regression, where we are given a data set that consists of a string attribute and an objective numerical attribute. The problem is to find the best string pattern that divides the data set in such a way that the distribution of the numerical attribute values of the set for which the pattern matches the string attribute, is most distinct, with respect to some appropriate measure, from the distribution of the numerical attribute values of the set for which the pattern does not match the string attribute. By solving this problem, we are able to discover, at the same time, a subset of the data whose objective numerical attributes are significantly different from rest of the data, as well as the splitting rule in the form of a string pattern that is conserved in the subset. Although the problem can be solved in linear time for the substring pattern class, the problem is NP-hard in the general case (i.e. more complex patterns), and we present an exact but efficient branch-and-bound algorithm which is applicable to various pattern classes. We apply our algorithm to intron sequences of human, mouse, fly, and zebrafish, and show the practicality of our approach and algorithm. We also discuss possible extensions of our algorithm, as well as promising applications, such as microarray gene expression data.