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:Epigenetic sex differences and their resulting implications for human health have been studied for about a decade. The objective of this paper is to use permutation-based inference and a new ranked-based test statistic to identify sex-based epigenetic differences in the human DNA methylome. In particular, we examine whether we could identify separations between the female and male distributions of DNA methylation across hundred of thousands CpG sites in two independent cohorts, the Swedish Adoption Twin study and the Lamarck study. Based on Fisherian p-values, we set a threshold for methylation differences "worth further scrutiny". At this threshold, we were able to confirm previously-found CpG sites that stratify with respect to sex. These CpG sites with sex differences in DNA methylation should be further investigated for their possible contribution to various physiological and pathological functions in the human body. We followed-up our statistical analyses with a literature review in order to inform the proposed disease implications for the loci we uncovered.
| S-EPMC10491832 | 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