Comparison of Methods of Detection of Exceptional Sequences in Prokaryotic Genomes

---

I. S. Rusinov¹, A. S. Ershova^1,2,3, A. S. Karyagina^1,2,3, S. A. Spirin^1,4,5, and A. V. Alexeevski^1,4,5*

¹Belozersky Institute of Physico-Chemical Biology, Lomonosov Moscow State University, 119992 Moscow, Russia

²Gamaleya National Research Center of Epidemiology and Microbiology, Ministry of Health of the Russian Federation, 123098 Moscow, Russia

³All-Russia Research Institute of Agricultural Biotechnology, 127550 Moscow, Russia

⁴Institute of System Studies, 117281 Moscow, Russia

⁵Lomonosov Moscow State University, Faculty of Bioengineering and Bioinformatics, 119991 Moscow, Russia; E-mail: aba@belozersky.msu.ru

^* To whom correspondence should be addressed.

Received June 7, 2017; Revision received November 10, 2017

---

Many proteins need recognition of specific DNA sequences for functioning. The number of recognition sites and their distribution along the DNA might be of biological importance. For example, the number of restriction sites is often reduced in prokaryotic and phage genomes to decrease the probability of DNA cleavage by restriction endonucleases. We call a sequence an exceptional one if its frequency in a genome significantly differs from one predicted by some mathematical model. An exceptional sequence could be either under- or over-represented, depending on its frequency in comparison with the predicted one. Exceptional sequences could be considered biologically meaningful, for example, as targets of DNA-binding proteins or as parts of abundant repetitive elements. Several methods to predict frequency of a short sequence in a genome, based on actual frequencies of certain its subsequences, are used. The most popular are methods based on Markov chain models. But any rigorous comparison of the methods has not previously been performed. We compared three methods for the prediction of short sequence frequencies: the maximum-order Markov chain model-based method, the method that uses geometric mean of extended Markovian estimates, and the method that utilizes frequencies of all subsequences including discontiguous ones. We applied them to restriction sites in complete genomes of 2500 prokaryotic species and demonstrated that the results depend greatly on the method used: lists of 5% of the most under-represented sites differed by up to 50%. The method designed by Burge and coauthors in 1992, which utilizes all subsequences of the sequence, showed a higher precision than the other two methods both on prokaryotic genomes and randomly generated sequences after computational imitation of selective pressure. We propose this method as the first choice for detection of exceptional sequences in prokaryotic genomes.

---

KEY WORDS: DNA sequence, prokaryotic genome, compositional bias, Markov chain model, restriction–modification system, restriction sites

DOI: 10.1134/S0006297918020050

---