An efficient rank based approach for closest string and closest substring.
Ontology highlight
ABSTRACT:
SUBMITTER: Dinu LP
PROVIDER: S-EPMC3366991 | biostudies-literature | 2012
REPOSITORIES: biostudies-literature
Publications
An efficient rank based approach for closest string and closest substring.
Dinu Liviu P LP Ionescu Radu R
PloS one 20120604 6
This paper aims to present a new genetic approach that uses rank distance for solving two known NP-hard problems, and to compare rank distance with other distance measures for strings. The two NP-hard problems we are trying to solve are closest string and closest substring. For each problem we build a genetic algorithm and we describe the genetic operations involved. Both genetic algorithms use a fitness function based on rank distance. We compare our algorithms with other genetic algorithms tha ...[more]
Similar Datasets
Project description:The string-matching paradigm is applied in every computer science and science branch in general. The existence of a plethora of string-matching algorithms makes it hard to choose the best one for any particular case. Expressing, measuring, and testing algorithm efficiency is a challenging task with many potential pitfalls. Algorithm efficiency can be measured based on the usage of different resources. In software engineering, algorithmic productivity is a property of an algorithm execution identified with the computational resources the algorithm consumes. Resource usage in algorithm execution could be determined, and for maximum efficiency, the goal is to minimize resource usage. Guided by the fact that standard measures of algorithm efficiency, such as execution time, directly depend on the number of executed actions. Without touching the problematics of computer power consumption or memory, which also depends on the algorithm type and the techniques used in algorithm development, we have developed a methodology which enables the researchers to choose an efficient algorithm for a specific domain. String searching algorithms efficiency is usually observed independently from the domain texts being searched. This research paper aims to present the idea that algorithm efficiency depends on the properties of searched string and properties of the texts being searched, accompanied by the theoretical analysis of the proposed approach. In the proposed methodology, algorithm efficiency is expressed through character comparison count metrics. The character comparison count metrics is a formal quantitative measure independent of algorithm implementation subtleties and computer platform differences. The model is developed for a particular problem domain by using appropriate domain data (patterns and texts) and provides for a specific domain the ranking of algorithms according to the patterns' entropy. The proposed approach is limited to on-line exact string-matching problems based on information entropy for a search pattern. Meticulous empirical testing depicts the methodology implementation and purports soundness of the methodology.
| S-EPMC7824336 | biostudies-literature
Project description:BACKGROUND: Ongoing improvements in throughput of the next-generation sequencing technologies challenge the current generation of de novo sequence assemblers. Most recent sequence assemblers are based on the construction of a de Bruijn graph. An alternative framework of growing interest is the assembly string graph, not necessitating a division of the reads into k-mers, but requiring fast algorithms for the computation of suffix-prefix matches among all pairs of reads. RESULTS: Here we present efficient methods for the construction of a string graph from a set of sequencing reads. Our approach employs suffix sorting and scanning methods to compute suffix-prefix matches. Transitive edges are recognized and eliminated early in the process and the graph is efficiently constructed including irreducible edges only. CONCLUSIONS: Our suffix-prefix match determination and string graph construction algorithms have been implemented in the software package Readjoiner. Comparison with existing string graph-based assemblers shows that Readjoiner is faster and more space efficient. Readjoiner is available at http://www.zbh.uni-hamburg.de/readjoiner.
| S-EPMC3507659 | biostudies-literature
Project description:MOTIVATION:Personal genomes carry inherent privacy risks and protecting privacy poses major social and technological challenges. We consider the case where a user searches for genetic information (e.g. an allele) on a server that stores a large genomic database and aims to receive allele-associated information. The user would like to keep the query and result private and the server the database. APPROACH:We propose a novel approach that combines efficient string data structures such as the Burrows-Wheeler transform with cryptographic techniques based on additive homomorphic encryption. We assume that the sequence data is searchable in efficient iterative query operations over a large indexed dictionary, for instance, from large genome collections and employing the (positional) Burrows-Wheeler transform. We use a technique called oblivious transfer that is based on additive homomorphic encryption to conceal the sequence query and the genomic region of interest in positional queries. RESULTS:We designed and implemented an efficient algorithm for searching sequences of SNPs in large genome databases. During search, the user can only identify the longest match while the server does not learn which sequence of SNPs the user queried. In an experiment based on 2184 aligned haploid genomes from the 1000 Genomes Project, our algorithm was able to perform typical queries within [Formula: see text] 4.6?s and [Formula: see text] 10.8?s for client and server side, respectively, on laptop computers. The presented algorithm is at least one order of magnitude faster than an exhaustive baseline algorithm. AVAILABILITY AND IMPLEMENTATION:https://github.com/iskana/PBWT-sec and https://github.com/ratschlab/PBWT-sec CONTACTS:shimizu-kana@aist.go.jp or Gunnar.Ratsch@ratschlab.org SUPPLEMENTARY INFORMATION:Supplementary data are available at Bioinformatics online.
| S-EPMC4892414 | biostudies-literature
Project description:A major task in computational biology is the discovery of short recurring string patterns known as motifs. Most of the schemes to discover motifs are either stochastic or combinatorial in nature. Stochastic approaches do not guarantee finding the correct motifs, while the combinatorial schemes tend to have an exponential time complexity with respect to motif length. To alleviate the cost, the combinatorial approach exploits dynamic data structures such as trees or graphs. Recently (Karci (2009) Efficient automatic exact motif discovery algorithms for biological sequences, Expert Systems with Applications 36:7952-7963) devised a deterministic algorithm that finds all the identical copies of string motifs of all sizes [Formula: see text] in theoretical time complexity of [Formula: see text] and a space complexity of [Formula: see text] where [Formula: see text] is the length of the input sequence and [Formula: see text] is the length of the longest possible string motif. In this paper, we present a significant improvement on Karci's original algorithm. The algorithm that we propose reports all identical string motifs of sizes [Formula: see text] that occur at least [Formula: see text] times. Our algorithm starts with string motifs of size 2, and at each iteration it expands the candidate string motifs by one symbol throwing out those that occur less than [Formula: see text] times in the entire input sequence. We use a simple array and data encoding to achieve theoretical worst-case time complexity of [Formula: see text] and a space complexity of [Formula: see text] Encoding of the substrings can speed up the process of comparison between string motifs. Experimental results on random and real biological sequences confirm that our algorithm has indeed a linear time complexity and it is more scalable in terms of sequence length than the existing algorithms.
| S-EPMC4037181 | biostudies-literature
Project description:In big data area a significant challenge about string similarity join is to find all similar pairs more efficiently. In this paper, we propose a parallel processing framework for efficient string similarity join. First, the input is split into some disjoint small subsets according to the joint frequency distribution and the interval distribution of strings. Then the filter-verification strategy is adopted in the computation of string similarity for each subset so that the number of candidate pairs is reduced before an effective pruning strategy is used to improve the performance. Finally, the operation of string join is executed in parallel. Para-Join algorithm based on the multi-threading technique is proposed to implement the framework in a multi-core system while Pada-Join algorithm based on Spark platform is proposed to implement the framework in a cluster system. We prove that Para-Join and Pada-Join cannot only avoid reduplicate computation but also ensure the completeness of the result. Experimental results show that Para-Join can achieve high efficiency and significantly outperform than state-of-the-art approaches, meanwhile, Pada-Join can work on large datasets.
| S-EPMC5344375 | biostudies-other
Project description:The increase in incidence of obesity and chronic diseases and their health care costs have raised the importance of quality diet on the health policy agendas. The healthy eating index is an important measure for diet quality which consists of 12 components derived from ratios of dependent variables with distributions hard to specify, measurement errors and excessive zero observations difficult to model parametrically. Hypothesis testing involving data of such nature poses challenges because the widely used multiple comparison procedures such as Hotelling's T(2) test and Bonferroni correction may suffer from substantial loss of efficiency. We propose a marginal rank-based inverse normal transformation approach to normalizing the marginal distribution of the data before employing a multivariate test procedure. Extensive simulation was conducted to demonstrate the ability of the proposed approach to adequately control the type I error rate as well as increase the power of the test, with data particularly from non-symmetric or heavy-tailed distributions. The methods are exemplified with data from a dietary intervention study for type I diabetic children. Published 2016. This article is a U.S. Government work and is in the public domain in the USA.
| S-EPMC4938741 | biostudies-literature
Project description:PREMISE OF THE STUDY:Difficulties inherent in microscopic pollen identification have resulted in limited implementation for large-scale studies. Metabarcoding, a relatively novel approach, could make pollen analysis less onerous; however, improved understanding of the quantitative capacity of various plant metabarcode regions and primer sets is needed to ensure that such applications are accurate and precise. METHODS AND RESULTS:We applied metabarcoding, targeting the ITS2, matK, and rbcL loci, to characterize six samples of pollen collected by honey bees, Apis mellifera. Additionally, samples were analyzed by light microscopy. We found significant rank-based associations between the relative abundance of pollen types within our samples as inferred by the two methods. CONCLUSIONS:Our findings suggest metabarcoding data from plastid loci, as opposed to the ribosomal locus, are more reliable for quantitative characterization of pollen assemblages. Furthermore, multilocus metabarcoding of pollen may be more reliable than single-locus analyses, underscoring the need for discovering novel barcodes and barcode combinations optimized for molecular palynology.
| S-EPMC4651628 | biostudies-literature
Project description:In this work, we study two approaches for the problem of RNA-Protein Interaction (RPI). In the first approach, we use a feature-based technique by combining extracted features from both sequences and secondary structures. The feature-based approach enhanced the prediction accuracy as it included much more available information about the RNA-protein pairs. In the second approach, we apply search algorithms and data structures to extract effective string patterns for prediction of RPI, using both sequence information (protein and RNA sequences), and structure information (protein and RNA secondary structures). This led to different string-based models for predicting interacting RNA-protein pairs. We show results that demonstrate the effectiveness of the proposed approaches, including comparative results against leading state-of-the-art methods.
| S-EPMC6017419 | biostudies-literature
Project description:In 2015, the United Nations established the Agenda 2030 for sustainable development, addressing the major challenges the world faces and introducing the 17 Sustainable Development Goals (SDGs). How are countries performing in their challenge toward sustainable development? We address this question by treating countries and Goals as a complex bipartite network. While network science has been used to unveil the interconnections among the Goals, it has been poorly exploited to rank countries for their achievements. In this work, we show that the network representation of the countries-SDGs relations as a bipartite system allows one to recover aggregate scores of countries' capacity to cope with SDGs as the solutions of a network's centrality exercise. While the Goals are all equally important by definition, interesting differences self-emerge when non-standard centrality metrics, borrowed from economic complexity, are adopted. Innovation and Climate Action stand as contrasting Goals to be accomplished, with countries facing the well-known trade-offs between economic and environmental issues even in addressing the Agenda. In conclusion, the complexity of countries' paths toward sustainable development cannot be fully understood by resorting to a single, multipurpose ranking indicator, while multi-variable analyses shed new light on the present and future of sustainable development.
| S-EPMC8322206 | biostudies-literature
Project description:Recent advances in large-scale gene expression profiling necessitate concurrent development of biostatistical approaches to reveal meaningful biological relationships. Most analyses rely on significance thresholds for identifying differentially expressed genes. We use an approach to compare gene expression datasets using 'threshold-free' comparisons. Significance cut-offs to identify genes shared between datasets may be too stringent and may miss concordant patterns of gene expression with potential biological relevance. A threshold-free approach gaining popularity in several research areas, including neuroscience, is Rank-Rank Hypergeometric Overlap (RRHO). Genes are ranked by their p-value and effect size direction, and ranked lists are compared to identify significantly overlapping genes across a continuous significance gradient rather than at a single arbitrary cut-off. We have updated the previous RRHO analysis by accurately detecting overlap of genes changed in the same and opposite directions between two datasets. Here, we use simulated and real data to show the drawbacks of the previous algorithm as well as the utility of our new algorithm. For example, we show the power of detecting discordant transcriptional patterns in the postmortem brain of subjects with psychiatric disorders. The new R package, RRHO2, offers a new, more intuitive visualization of concordant and discordant gene overlap.
| S-EPMC6018631 | biostudies-literature