Browse
Submit Data
Databases
API
Help

Dataset Information

0 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

The distribution of word matches between Markovian sequences with periodic boundary conditions.

ABSTRACT: Word match counts have traditionally been proposed as an alignment-free measure of similarity for biological sequences. The D(2) statistic, which simply counts the number of exact word matches between two sequences, is a useful test bed for developing rigorous mathematical results, which can then be extended to more biologically useful measures. The distributional properties of the D(2) statistic under the null hypothesis of identically and independently distributed letters have been studied extensively, but no comprehensive study of the D(2) distribution for biologically more realistic higher-order Markovian sequences exists. Here we derive exact formulas for the mean and variance of the D(2) statistic for Markovian sequences of any order, and demonstrate through Monte Carlo simulations that the entire distribution is accurately characterized by a Pólya-Aeppli distribution for sequence lengths of biological interest. The approach is novel in that Markovian dependency is defined for sequences with periodic boundary conditions, and this enables exact analytic formulas for the mean and variance to be derived. We also carry out a preliminary comparison between the approximate D(2) distribution computed with the theoretical mean and variance under a Markovian hypothesis and an empirical D(2) distribution from the human genome.

SUBMITTER: Burden CJ

PROVIDER: S-EPMC3880068 | biostudies-literature | 2014 Jan

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Similar Datasets

Asymptotic behaviour and optimal word size for exact and approximate word matches between random sequences.

Project description:BackgroundThe number of k-words shared between two sequences is a simple and efficient alignment-free sequence comparison method. This statistic, D2, has been used for the clustering of EST sequences. Sequence comparison based on D2 is extremely fast, its runtime is proportional to the size of the sequences under scrutiny, whereas alignment-based comparisons have a worst-case run time proportional to the square of the size. Recent studies have tackled the rigorous study of the statistical distribution of D2, and asymptotic regimes have been derived. The distribution of approximate k-word matches has also been studied.ResultsWe have computed the D2 optimal word size for various sequence lengths, and for both perfect and approximate word matches. Kolmogorov-Smirnov tests show D2 to have a compound Poisson distribution at the optimal word size for small sequence lengths (below 400 letters) and a normal distribution at the optimal word size for large sequence lengths (above 1600 letters). We find that the D2 statistic outperforms BLAST in the comparison of artificially evolved sequences, and performs similarly to other methods based on exact word matches. These results obtained with randomly generated sequences are also valid for sequences derived from human genomic DNA.ConclusionWe have characterized the distribution of the D2 statistic at optimal word sizes. We find that the best trade-off between computational efficiency and accuracy is obtained with exact word matches. Given that our numerical tests have not included sequence shuffling, transposition or splicing, the improvements over existing methods reported here underestimate that expected in real sequences. Because of the linear run time and of the known normal asymptotic behavior, D2-based methods are most appropriate for large genomic sequences.

| S-EPMC1764478 | biostudies-literature

Structural Anisotropy in Polar Fluids Subjected to Periodic Boundary Conditions.

Project description:A heuristic model based on dielectric continuum theory for the long-range solvation free energy of a dipolar system possessing periodic boundary conditions (PBCs) is presented. The predictions of the model are compared to simulation results for Stockmayer fluids simulated using three different cell geometries. The boundary effects induced by the PBCs are shown to lead to anisotropies in the apparent dielectric constant and the long-range solvation free energy of as much as 50%. However, the sum of all of the anisotropic energy contributions yields a value that is very close to the isotropic one derived from dielectric continuum theory, leading to a total system energy close to the dielectric value. It is finally shown that the leading-order contribution to the energetic and structural anisotropy is significantly smaller in the noncubic simulation cell geometries compared to when using a cubic simulation cell.

| S-EPMC3269192 | biostudies-other

Electrically turning periodic structures in cholesteric layer with conical-planar boundary conditions.

Project description:Electro-optical cell based on the cholesteric liquid crystal is studied with unique combination of the boundary conditions: conical anchoring on the one substrate and planar anchoring on another one. Periodic structures in cholesteric layer and their transformation under applied electric field are considered by polarizing optical microscopy, the experimental findings are supported by the data of the calculations performed using the extended Frank elastic continuum approach. Such structures are the set of alternating over- and under-twisted defect lines whose azimuthal director angles differ by [Formula: see text]. The [Formula: see text] and [Formula: see text]-defects of periodicity, which are the smooth transition between the defect lines, are observed at the edge of electrode area. The growth direction of defect lines forming a diffraction grating can be controlled by applying a voltage in the range of [Formula: see text] V during the process. Resulting orientation and distance between the lines don't change under voltage. However, at [Formula: see text] V [Formula: see text]-defects move along the defect lines away from the electrode edges, and, finally, the grating lines collapse at the cell's center. These results open a way for the use of such cholesteric material in applications with periodic defect structures where a periodicity, orientation, and configuration of defects should be adjusted.

| S-EPMC8052423 | biostudies-literature

Accurate multiple alignment of distantly related genome sequences using filtered spaced word matches as anchor points.

Project description:MotivationMost methods for pairwise and multiple genome alignment use fast local homology search tools to identify anchor points, i.e. high-scoring local alignments of the input sequences. Sequence segments between those anchor points are then aligned with slower, more sensitive methods. Finding suitable anchor points is therefore crucial for genome sequence comparison; speed and sensitivity of genome alignment depend on the underlying anchoring methods.ResultsIn this article, we use filtered spaced word matches to generate anchor points for genome alignment. For a given binary pattern representing match and don't-care positions, we first search for spaced-word matches, i.e. ungapped local pairwise alignments with matching nucleotides at the match positions of the pattern and possible mismatches at the don't-care positions. Those spaced-word matches that have similarity scores above some threshold value are then extended using a standard X-drop algorithm; the resulting local alignments are used as anchor points. To evaluate this approach, we used the popular multiple-genome-alignment pipeline Mugsy and replaced the exact word matches that Mugsy uses as anchor points with our spaced-word-based anchor points. For closely related genome sequences, the two anchoring procedures lead to multiple alignments of similar quality. For distantly related genomes, however, alignments calculated with our filtered-spaced-word matches are superior to alignments produced with the original Mugsy program where exact word matches are used to find anchor points.Availability and implementationhttp://spacedanchor.gobics.de.Supplementary informationSupplementary data are available at Bioinformatics online.

| S-EPMC6330006 | biostudies-literature

Annotating large genomes with exact word matches.

Project description:We have developed a tool for rapidly determining the number of exact matches of any word within large, internally repetitive genomes or sets of genomes. Thus we can readily annotate any sequence, including the entire human genome, with the counts of its constituent words. We create a Burrows-Wheeler transform of the genome, which together with auxiliary data structures facilitating counting, can reside in about one gigabyte of RAM. Our original interest was motivated by oligonucleotide probe design, and we describe a general protocol for defining unique hybridization probes. But our method also has applications for the analysis of genome structure and assembly. We demonstrate the identification of chromosome-specific repeats, and outline a general procedure for finding undiscovered repeats. We also illustrate the changing contents of the human genome assemblies by comparing the annotations built from different genome freezes.

| S-EPMC403711 | biostudies-literature

Lipid and Peptide Diffusion in Bilayers: The Saffman-Delbruck Model and Periodic Boundary Conditions.

Project description:The periodic Saffman-Delbrück (PSD) model, an extension of the Saffman-Delbrück model developed to describe the effects of periodic boundary conditions on the diffusion constants of lipids and proteins obtained from simulation, is tested using the coarse-grained Martini and all-atom CHARMM36 (C36) force fields. Simulations of pure Martini dipalmitoylphosphatidylcholine (DPPC) bilayers and those with one embedded gramicidin A (gA) dimer or one gA monomer with sizes ranging from 512 to 2048 lipids support the PSD model. Underestimates of D? (the value of the diffusion constant for an infinite system) from the 512-lipid system are 35% for DPPC, 45% for the gA monomer, and 70% for the gA dimer. Simulations of all-atom DPPC and dioleoylphosphatidylcholine (DOPC) bilayers yield diffusion constants not far from experiment. However, the PSD model predicts that diffusion constants at the sizes of the simulation should underestimate experiment by approximately a factor of 3 for DPPC and 2 for DOPC. This likely implies a deficiency in the C36 force field. A Bayesian method for extrapolating diffusion constants of lipids and proteins in membranes obtained from simulation to infinite system size is provided.

| S-EPMC6326097 | biostudies-literature

Crystalline Moduli of Polymers, Evaluated from Density Functional Theory Calculations under Periodic Boundary Conditions.

Project description:A theoretical methodology based on quantum chemistry to calculate mechanical properties of polymer crystals has been developed and applied to representative polymers. By density functional theory calculations including a dispersion force correction under three-dimensional periodic boundary conditions, crystal structures of poly(methylene oxide) (PMO), polyethylene (PE), poly(ethylene terephthalate) (PET), poly(trimethylene terephthalate) (PTT), and poly(butylene terephthalate) (PBT) were optimized and their mechanical properties, such as crystalline moduli and linear and volume compressibilities, were calculated. The optimized crystal structures were proved to be fully consistent with those determined by X-ray and neutron diffraction. The crystalline moduli (E ∥) parallel to the chain axis were calculated to be 114 GPa (PMO), 333 GPa (PE), 182 GPa (PET), 7.1 GPa (PTT), and 20.8 GPa (PBT) and compared with those determined from X-ray diffraction, Raman spectroscopy, and neutron inelastic scattering experiments. Herein, the E ∥ values thus determined are interpreted in terms of conformational characteristics of the polymeric chains and the validity of the homogeneous stress hypothesis adopted in the X-ray diffraction method is also discussed.

| S-EPMC6641976 | biostudies-literature

Fast and accurate phylogeny reconstruction using filtered spaced-word matches.

Project description:MotivationWord-based or 'alignment-free' algorithms are increasingly used for phylogeny reconstruction and genome comparison, since they are much faster than traditional approaches that are based on full sequence alignments. Existing alignment-free programs, however, are less accurate than alignment-based methods.ResultsWe propose Filtered Spaced Word Matches (FSWM) , a fast alignment-free approach to estimate phylogenetic distances between large genomic sequences. For a pre-defined binary pattern of match and don't-care positions, FSWM rapidly identifies spaced word-matches between input sequences, i.e. gap-free local alignments with matching nucleotides at the match positions and with mismatches allowed at the don't-care positions. We then estimate the number of nucleotide substitutions per site by considering the nucleotides aligned at the don't-care positions of the identified spaced-word matches. To reduce the noise from spurious random matches, we use a filtering procedure where we discard all spaced-word matches for which the overall similarity between the aligned segments is below a threshold. We show that our approach can accurately estimate substitution frequencies even for distantly related sequences that cannot be analyzed with existing alignment-free methods; phylogenetic trees constructed with FSWM distances are of high quality. A program run on a pair of eukaryotic genomes of a few hundred Mb each takes a few minutes.Availability and implementationThe program source code for FSWM including a documentation, as well as the software that we used to generate artificial genome sequences are freely available at http://fswm.gobics.de/.Contactchris.leimeister@stud.uni-goettingen.de.Supplementary informationSupplementary data are available at Bioinformatics online.

| S-EPMC5409309 | biostudies-literature

Vibrations and energy distribution in inhomogeneous rods with elastic and viscous boundary conditions.

Project description:Functionally graded materials have broad engineering applications including mechanical engineering, electronics, chemistry, and biomedical engineering. One notable advantage of such materials is that their stiffness distribution can be optimized to avoid stress concentration. A novel approach for solving the equations describing the longitudinal vibration of functionally graded rods with viscous and elastic boundary conditions is proposed. The characteristic equation of the system is derived for the solution of the undamped case for the constant stiffness rod. Then, a homotopy method is applied to compute the eigenvalues and mode shapes of graded rods for viscoelastic boundary conditions. The changes of the eigenvalues and mode shapes as function of the damping parameters are investigated. The optimal damping of the system is computed. It is shown that the qualitative behavior depends on the relation between the actual damping and the optimal damping of the system. The energy density distribution of graded rods is also discussed. An energy measure, the mean scaled energy density distribution is introduced to characterize the energy distribution along the rod in the asymptotic time limit. The significance of such a measure is that it reveals how the energy tends to distribute along the rod. It is shown that the energy distribution can be manipulated by changing the damping parameters. Qualitative changes depending on the relation between the actual damping and the optimal damping are highlighted.

| S-EPMC10838305 | biostudies-literature