Dataset Information

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

ABSTRACT:

Background

The 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.

Results

We 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.

Conclusion

We 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.

SUBMITTER: Foret S

PROVIDER: S-EPMC1764478 | biostudies-literature | 2006 Dec

REPOSITORIES: biostudies-literature

ACCESS DATA

Publications

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

Forêt Sylvain S Kantorovitz Miriam R MR Burden Conrad J CJ

BMC bioinformatics 20061218

<h4>Background</h4>The 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 statistic ...[more]

PMID: 17254306

Similar Datasets

Project description:Body size, and, by extension, growth has impacts on physiology, survival, attainment of sexual maturity, fecundity, generation time, and population dynamics, especially in ectotherm animals that often exhibit extensive growth following attainment of sexual maturity. Frequently, growth is analyzed at the population level, providing useful population mean growth parameters but ignoring individual variation that is also of ecological and evolutionary significance. Our long-term study of Lake Erie Watersnakes, Nerodia sipedon insularum, provides data sufficient for a detailed analysis of population and individual growth. We describe population mean growth separately for males and females based on size of known age individuals (847 captures of 769 males, 748 captures of 684 females) and annual growth increments of individuals of unknown age (1,152 males, 730 females). We characterize individual variation in asymptotic size based on repeated measurements of 69 males and 71 females that were each captured in five to nine different years. The most striking result of our analyses is that asymptotic size varies dramatically among individuals, ranging from 631-820 mm snout-vent length in males and from 835-1125 mm in females. Because female fecundity increases with increasing body size, we explore the impact of individual variation in asymptotic size on lifetime reproductive success using a range of realistic estimates of annual survival. When all females commence reproduction at the same age, lifetime reproductive success is greatest for females with greater asymptotic size regardless of annual survival. But when reproduction is delayed in females with greater asymptotic size, lifetime reproductive success is greatest for females with lower asymptotic size when annual survival is low. Possible causes of individual variation in asymptotic size, including individual- and cohort-specific variation in size at birth and early growth, warrant further investigation.

Dataset Information

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

Background

Results

Conclusion

Publications

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

Similar Datasets

OmicsDI is part of the ELIXIR infrastructure