Lower Density Selection Schemes via Small Universal Hitting Sets with Short Remaining Path Length.
Ontology highlight
ABSTRACT:
SUBMITTER: Zheng H
PROVIDER: S-EPMC8066347 | biostudies-literature |
REPOSITORIES: biostudies-literature
Similar Datasets
Project description:With the rapidly increasing volume of deep sequencing data, more efficient algorithms and data structures are needed. Minimizers are a central recent paradigm that has improved various sequence analysis tasks, including hashing for faster read overlap detection, sparse suffix arrays for creating smaller indexes, and Bloom filters for speeding up sequence search. Here, we propose an alternative paradigm that can lead to substantial further improvement in these and other tasks. For integers k and L > k, we say that a set of k-mers is a universal hitting set (UHS) if every possible L-long sequence must contain a k-mer from the set. We develop a heuristic called DOCKS to find a compact UHS, which works in two phases: The first phase is solved optimally, and for the second we propose several efficient heuristics, trading set size for speed and memory. The use of heuristics is motivated by showing the NP-hardness of a closely related problem. We show that DOCKS works well in practice and produces UHSs that are very close to a theoretical lower bound. We present results for various values of k and L and by applying them to real genomes show that UHSs indeed improve over minimizers. In particular, DOCKS uses less than 30% of the 10-mers needed to span the human genome compared to minimizers. The software and computed UHSs are freely available at github.com/Shamir-Lab/DOCKS/ and acgt.cs.tau.ac.il/docks/, respectively.
| S-EPMC5645146 | biostudies-literature
Project description:Influenza viruses have a huge impact on public health. Current influenza vaccines need to be updated annually and protect poorly against antigenic drift variants or novel emerging subtypes. Vaccination against influenza can be improved in two important ways, either by inducing more broadly protective immune responses or by decreasing the time of vaccine production, which is relevant especially during a pandemic outbreak. In this review, we outline the current efforts to develop so-called "universal influenza vaccines", describing antigens that may induce broadly protective immunity and novel vaccine production platforms that facilitate timely availability of vaccines.
| S-EPMC4494343 | biostudies-other
Project description:BackgroundSegmental duplication is widely held to be an important mode of genome growth and evolution. Yet how this would affect the global structure of genomes has been little discussed.Methods/principal findingsHere, we show that equivalent length, or L(e), a quantity determined by the variance of fluctuating part of the distribution of the k-mer frequencies in a genome, characterizes the latter's global structure. We computed the L(e)s of 865 complete chromosomes and found that they have nearly universal but (k-dependent) values. The differences among the L(e) of a chromosome and those of its coding and non-coding parts were found to be slight.ConclusionsWe verified that these non-trivial results are natural consequences of a genome growth model characterized by random segmental duplication and random point mutation, but not of any model whose dominant growth mechanism is not segmental duplication. Our study also indicates that genomes have a nearly universal cumulative "point" mutation density of about 0.73 mutations per site that is compatible with the relatively low mutation rates of (1-5) x 10(-3)/site/Mya previously determined by sequence comparison for the human and E. coli genomes.
| S-EPMC2854691 | biostudies-literature
Project description:Given a sample of n data points and an n by n dissimilarity matrix, data seriation methods produce a linear ordering of the objects, putting similar objects nearby in the ordering. One may visualize the reordered dissimilarity matrix with a heat map and thus understand the structure of the data, while still displaying the full matrix of dissimilarities. Good orderings produce heat maps that are easy to read and allow for clear interpretation. We consider two popular seriation methods, minimizing path length by solving the Traveling Salesman Problem (TSP), and Optimal Leaf Ordering (OLO), which minimizes path length among all orderings consistent with a given tree structure. Learning from the strengths and weaknesses of the two methods, we introduce a new hybrid seriation method, tree-penalized Path Length (tpPL). The objective is a linear combination of path length and the extent of violations of the tree structure, with a parameter that transitions the optimal paths smoothly from TSP to OLO. We present a detailed study over 44 synthetic datasets which are designed to bring out the strengths and weaknesses of the three methods, finding that the hybrid nature of tpPL enables it to overcome the weaknesses of TSP and OLO.
| S-EPMC9642984 | biostudies-literature
Project description:The bacterial flagellum exemplifies a system where even small deviations from the highly regulated flagellar assembly process can abolish motility and cause negative physiological outcomes. Consequently, bacteria have evolved elegant and robust regulatory mechanisms to ensure that flagellar morphogenesis follows a defined path, with each component self-assembling to predetermined dimensions. The flagellar rod acts as a driveshaft to transmit torque from the cytoplasmic rotor to the external filament. The rod self-assembles to a defined length of ~25 nanometers. Here, we provide evidence that rod length is limited by the width of the periplasmic space between the inner and outer membranes. The length of Braun's lipoprotein determines periplasmic width by tethering the outer membrane to the peptidoglycan layer.
| S-EPMC5963725 | biostudies-literature
Project description:The GORE EXCLUDER Iliac Branch Endoprosthesis (IBE; W. L. Gore and Associates, Flagstaff, AZ, USA) applicability is limited by the aorto-iliac length (AOL). The shortage may be a major exclusion criterion. An 85-year-old male presented with an abdominal aortic and left common iliac arterial aneurysm. The left-side AOL was 146-mm, which was deemed 19-mm too short for IBE usage. To increase implantation length, the contra-lateral connection stent graft was deployed along the implantation line, wound half-circumferentially around the ipsilateral limb. Any form of endoleak, limb occlusion, and device migration has not been observed for twelve months.
| S-EPMC6766775 | biostudies-literature
Project description:Animals are capable of navigation even in the absence of prominent landmark cues. This behavioral demonstration of path integration is supported by the discovery of place cells and other neurons that show path-invariant response properties even in the dark. That is, under suitable conditions, the activity of these neurons depends primarily on the spatial location of the animal regardless of which trajectory it followed to reach that position. Although many models of path integration have been proposed, no known single theoretical framework can formally accommodate their diverse computational mechanisms. Here we derive a set of necessary and sufficient conditions for a general class of systems that performs exact path integration. These conditions include multiplicative modulation by velocity inputs and a path-invariance condition that limits the structure of connections in the underlying neural network. In particular, for a linear system to satisfy the path-invariance condition, the effective synaptic weight matrices under different velocities must commute. Our theory subsumes several existing exact path integration models as special cases. We use entorhinal grid cells as an example to demonstrate that our framework can provide useful guidance for finding unexpected solutions to the path integration problem. This framework may help constrain future experimental and modeling studies pertaining to a broad class of neural integration systems.
| S-EPMC3340063 | biostudies-literature
Project description:MotivationRecent technological advances have led to an increase in the production and availability of single-cell data. The ability to integrate a set of multi-technology measurements would allow the identification of biologically or clinically meaningful observations through the unification of the perspectives afforded by each technology. In most cases, however, profiling technologies consume the used cells and thus pairwise correspondences between datasets are lost. Due to the sheer size single-cell datasets can acquire, scalable algorithms that are able to universally match single-cell measurements carried out in one cell to its corresponding sibling in another technology are needed.ResultsWe propose Single-Cell data Integration via Matching (SCIM), a scalable approach to recover such correspondences in two or more technologies. SCIM assumes that cells share a common (low-dimensional) underlying structure and that the underlying cell distribution is approximately constant across technologies. It constructs a technology-invariant latent space using an autoencoder framework with an adversarial objective. Multi-modal datasets are integrated by pairing cells across technologies using a bipartite matching scheme that operates on the low-dimensional latent representations. We evaluate SCIM on a simulated cellular branching process and show that the cell-to-cell matches derived by SCIM reflect the same pseudotime on the simulated dataset. Moreover, we apply our method to two real-world scenarios, a melanoma tumor sample and a human bone marrow sample, where we pair cells from a scRNA dataset to their sibling cells in a CyTOF dataset achieving 90% and 78% cell-matching accuracy for each one of the samples, respectively.Availability and implementationhttps://github.com/ratschlab/scim.Supplementary informationSupplementary data are available at Bioinformatics online.
| S-EPMC7773480 | biostudies-literature
Project description:How might a smooth probability distribution be estimated with accurately quantified uncertainty from a limited amount of sampled data? Here we describe a field-theoretic approach that addresses this problem remarkably well in one dimension, providing an exact nonparametric Bayesian posterior without relying on tunable parameters or large-data approximations. Strong non-Gaussian constraints, which require a nonperturbative treatment, are found to play a major role in reducing distribution uncertainty. A software implementation of this method is provided.
| S-EPMC6487661 | biostudies-literature
Project description:Early detection of coronary artery disease (CAD) using the acoustic approach, a noninvasive and cost-effective method, would greatly improve the outcome of CAD patients. To detect CAD, we analyze diastolic sounds for possible CAD murmurs. We observed diastolic sounds to exhibit 1/f structure and developed a new method, path length entropy (PLE) and a scaled version (SPLE), to characterize this structure to improve CAD detection. We compare SPLE results to Hurst exponent, Sample entropy and Multiscale entropy for distinguishing between normal and CAD patients. SPLE achieved a sensitivity-specificity of 80%-81%, the best of the tested methods. However, PLE and SPLE are not sufficient to prove nonlinearity, and evaluation using surrogate data suggests that our cardiovascular sound recordings do not contain significant nonlinear properties.
| S-EPMC3741681 | biostudies-literature