Search results for "Sorting"
showing 10 items of 187 documents
Sorting suffixes of a text via its Lyndon Factorization
2013
The process of sorting the suffixes of a text plays a fundamental role in Text Algorithms. They are used for instance in the constructions of the Burrows-Wheeler transform and the suffix array, widely used in several fields of Computer Science. For this reason, several recent researches have been devoted to finding new strategies to obtain effective methods for such a sorting. In this paper we introduce a new methodology in which an important role is played by the Lyndon factorization, so that the local suffixes inside factors detected by this factorization keep their mutual order when extended to the suffixes of the whole word. This property suggests a versatile technique that easily can b…
Large-scale compression of genomic sequence databases with the Burrows-Wheeler transform
2012
Motivation The Burrows-Wheeler transform (BWT) is the foundation of many algorithms for compression and indexing of text data, but the cost of computing the BWT of very large string collections has prevented these techniques from being widely applied to the large sets of sequences often encountered as the outcome of DNA sequencing experiments. In previous work, we presented a novel algorithm that allows the BWT of human genome scale data to be computed on very moderate hardware, thus enabling us to investigate the BWT as a tool for the compression of such datasets. Results We first used simulated reads to explore the relationship between the level of compression and the error rate, the leng…
Comparison of spike parameters from optically identified GABAergic and glutamatergic neurons in sparse cortical cultures
2015
We are pleased to note that our publication “Comparison of spike parameters from optically identified GABAergic and glutamatergic neurons in sparse cortical cultures” by Weir et al. (2015) raised some discussion on the feasibility of solely electrophysiological discrimination of distinct neuronal subpopulations in vitro. We agree with Becchetti and Wanke (2015) that their report and our study on the same question were conducted with different technical approaches and that this may explain the observed differences between both studies. Although we obviously recorded a reduced spontaneous neuronal activity under our sparse culture conditions, these conditions were necessary to enable the uneq…
Sorted deduplication: How to process thousands of backup streams
2016
The requirements of deduplication systems have changed in the last years. Early deduplication systems had to process dozens to hundreds of backup streams at the same time while today they are able to process hundreds to thousands of them. Traditional approaches rely on stream-locality, which supports parallelism, but which easily leads to many non-contiguous disk accesses, as each stream competes with all other streams for the available resources. This paper presents a new exact deduplication approach designed for processing thousands of backup streams at the same time on the same fingerprint index. The underlying approach destroys the traditionally exploited temporal chunk locality and cre…
Fuzzy fixed points of generalized F2-geraghty type fuzzy mappings and complementary results
2016
The aim of this paper is to introduce generalized F2-Geraghty type fuzzy mappings on a metric space for establishing the existence of fuzzy fixed points of such mappings. As an application of our result, we obtain the existence of common fuzzy fixed point for a generalized F2-Geraghty type fuzzy hybrid pair. These results unify, generalize and complement various known comparable results in the literature. An example and an application to theoretical computer science are presented to support the theory proved herein. Also, to suggest further research on fuzzy mappings, a Feng–Liu type theorem is proved.
Spatial discontinuity of Optomotor-blind expression in the Drosophila wing imaginal disc disrupts epithelial architecture and promotes cell sorting
2010
Abstract Background Decapentaplegic (Dpp) is one of the best characterized morphogens, required for dorso-ventral patterning of the Drosophila embryo and for anterior-posterior (A/P) patterning of the wing imaginal disc. In the larval wing pouch, the Dpp target gene optomotor-blind (omb) is generally assumed to be expressed in a step function above a certain threshold of Dpp signaling activity. Results We show that the transcription factor Omb forms, in fact, a symmetrical gradient on both sides of the A/P compartment boundary. Disruptions of the Omb gradient lead to a re-organization of the epithelial cytoskeleton and to a retraction of cells toward the basal membrane suggesting that the O…
Hepatitis B virus maturation is sensitive to functional inhibition of ESCRT-III, Vps4, and gamma 2-adaptin.
2007
ABSTRACT Hepatitis B virus (HBV) is an enveloped DNA virus that presumably buds at intracellular membranes of infected cells. HBV budding involves two endocytic host proteins, the ubiquitin-interacting adaptor γ2-adaptin and the Nedd4 ubiquitin ligase. Here, we demonstrate that HBV release also requires the cellular machinery that generates internal vesicles of multivesicular bodies (MVBs). In order to perturb the MVB machinery in HBV-replicating liver cells, we used ectopic expression of dominant-negative mutants of different MVB components, like the ESCRT-III complex-forming CHMP proteins and the Vps4 ATPases. Upon coexpression of mutated CHMP3, CHMP4B, or CHMP4C forms, as well as of ATPa…
Quantum Algorithms for Some Strings Problems Based on Quantum String Comparator
2022
We study algorithms for solving three problems on strings. These are sorting of n strings of length k, “the Most Frequent String Search Problem”, and “searching intersection of two sequences of strings”. We construct quantum algorithms that are faster than classical (randomized or deterministic) counterparts for each of these problems. The quantum algorithms are based on the quantum procedure for comparing two strings of length k in O(k) queries. The first problem is sorting n strings of length k. We show that classical complexity of the problem is Θ(nk) for constant size alphabet, but our quantum algorithm has O˜(nk) complexity. The second one is searching the most frequent string among n …
Multiparametric characterization by flow cytometry of flow-sorted subpopulations of a human hepatoma cell line useful for drug research
2004
Background Primary cultured hepatocytes are the closest model to the liver for drug research. However, to overcome its limited availability, the search for hepatic cell lines as an alternative to primary cultures is a matter of current interest. In particular, highly differentiated hepatocellular carcinomas have been proposed as in vitro tools for routine experiments in hepatotoxicity and drug metabolism. Methods Cell populations were selected by fluorescence-activated cell sorting based on low and high relative expressions of P-glycoprotein. These cell lines were characterized after 21 days in culture by multiparametric analysis with flow cytometry providing direct information on key cellu…
Primary Structure of Selected Archaeal Mesophilic and Extremely Thermophilic Outer Surface Layer Proteins
2002
The archaea are recognized as a separate third domain of life together with the bacteria and eucarya. The archaea include the methanogens, extreme halophiles, thermoplasmas, Sulfate reducers and Sulfur metabolizing thermophiles, which thrive in different habitats such as anaerobic niches, salt lakes, and marine hydrothermals systems and continental solfataras. Many of these habitats represent extreme environments in respect to temperature, osmotic pressure and pH-values and remind on the conditions of the early earth. The cell envelope structures were one of the first biochemical characteristics of archaea studied in detail. The most common archaeal cell envelope is composed of a single cry…