Geodesic
Alignment of a hidden palindrome
Matematičeskaâ biologiâ i bioinformatika, Tome 19 (2024), pp. 427-438.

Voir la notice de l'article provenant de la source Math-Net.Ru

The aim of the work is to generalize known algorithms to solve new problems arising in bioinformatics. We consider algorithms for optimizing the edit distance between sequences, the first of which is known and the second is a hidden palindrome of arbitrary length. It is important that the length of the desired palindrome is determined as a result of optimization. In the first task, it is necessary to select a palindrome from the ensemble of palindromes defined by the second input sequence. In this case, the original sequences may not contain the desired palindrome entirely. But the second sequence contains half of the desired palindrome. The first input sequence is used for optimization. In another task, such a palindrome may be partial, that is, only a prefix is complementary to a suffix. Such a partial palindrome forms a hairpin. The new algorithms run in quadratic time, which is faster than exhaustive search of admissible palindromes. The algorithms essentially exploit the linear dependence of the edit distance on the length of a continuous deletion or insertion. On the other hand, the algorithm for solving the first task allows us to calculate the similarity of a given sequence to any palindrome. However, in general, comparing two different sequences does not reduce to finding palindromes in each of them. Fast search for suboptimal solutions is also discussed. Software implementations of the considered algorithms are created. They are available at lab6.iitp.ru/~/pali. Some examples of nucleotide sequences with degenerate inverted repeats are given. In particular, we consider inverted repeats in noncoding regions of plastid DNA in flowering plants as well as microRNA genes. The possible application of our method to the search for conservative secondary structures of RNA is also discussed. 
@article{MBB_2024_19_a5,
     author = {O. A. Zverkov and A. V. Seliverstov and G. A. Shilovsky},
     title = {Alignment of a hidden palindrome},
     journal = {Matemati\v{c}eska\^a biologi\^a i bioinformatika},
     pages = {427--438},
     publisher = {mathdoc},
     volume = {19},
     year = {2024},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/MBB_2024_19_a5/}
}
TY  - JOUR
AU  - O. A. Zverkov
AU  - A. V. Seliverstov
AU  - G. A. Shilovsky
TI  - Alignment of a hidden palindrome
JO  - Matematičeskaâ biologiâ i bioinformatika
PY  - 2024
SP  - 427
EP  - 438
VL  - 19
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/MBB_2024_19_a5/
LA  - ru
ID  - MBB_2024_19_a5
ER  - 
%0 Journal Article
%A O. A. Zverkov
%A A. V. Seliverstov
%A G. A. Shilovsky
%T Alignment of a hidden palindrome
%J Matematičeskaâ biologiâ i bioinformatika
%D 2024
%P 427-438
%V 19
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MBB_2024_19_a5/
%G ru
%F MBB_2024_19_a5
O. A. Zverkov; A. V. Seliverstov; G. A. Shilovsky. Alignment of a hidden palindrome. Matematičeskaâ biologiâ i bioinformatika, Tome 19 (2024), pp. 427-438. http://geodesic.mathdoc.fr/item/MBB_2024_19_a5/

[1] V. I. Levenshtein, “Dvoichnye kody s ispravleniem vypadenii, vstavok i zameschenii simvolov”, Doklady AN SSSR, 163:4 (1965), 845–848 <ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:0149.15905'>0149.15905</ext-link>

[2] Leontev V. K., “Vosstanovlenie tsiklicheskikh slov po fragmentam”, Problemy peredachi informatsii, 48:2 (2012), 121–126 <ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1274.68280'>1274.68280</ext-link>

[3] R. K. Tetuev, N. N. Nazipova, “Statisticheskaya model predskazaniya saitov svyazyvaniya TALEN s DNK na osnove skolzyaschego srednego”, Matem. biologiya i bioinform, 18:2 (2023), 621–645 <ext-link ext-link-type='doi' href='https://doi.org/10.17537/2023.18.621'>10.17537/2023.18.621</ext-link>

[4] L. Fu, Y. Cao, J. Wu, Q. Peng, Q. Nie, X. Xie, “UFold: fast and accurate RNA secondary structure prediction with deep learning”, Nucleic Acids Research, 50:3 (2022), e14 <ext-link ext-link-type='doi' href='https://doi.org/10.1093/nar/gkab1074'>10.1093/nar/gkab1074</ext-link>

[5] C. C. Chen, Y. M. Chan, “REDfold: accurate RNA secondary structure prediction using residual encoder-decoder network”, BMC Bioinformatics, 24 (2023), 1–13 <ext-link ext-link-type='doi' href='https://doi.org/10.1186/s12859-023-05238-8'>10.1186/s12859-023-05238-8</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:07918356'>07918356</ext-link>

[6] L. N. Grinkevich, “Rol mikroRNK v obuchenii i dolgovremennoi pamyati”, Vavilovskii zhurnal genetiki i selektsii, 24:8 (2020), 885–896 <ext-link ext-link-type='doi' href='https://doi.org/10.18699/VJ20.687'>10.18699/VJ20.687</ext-link>

[7] K. V. Mikhailov, B. D. Efeykin, A. Y. Panchin, D. A. Knorre, M. D. Logacheva, A. A. Penin, M. S. Muntyan, M. A. Nikitin, O. V. Popova, O. N. Zanegina, M. Y. Vyssokikh, S. E. Spiridonov, V. V. Aleoshin, Y. V. Panchin, “Coding palindromes in mitochondrial genes of Nematomorpha”, Nucleic Acids Research, 47:13 (2019), 6858–6870 <ext-link ext-link-type='doi' href='https://doi.org/10.1093/nar/gkz517'>10.1093/nar/gkz517</ext-link>

[8] Nikolaeva O. V., Beregova A. M., Efeykin B. D., Miroliubova T. S., Zhuravlev A. Yu., A. Yu. Ivantsov, K. V. Mikhailov, S. E. Spiridonov, V. V. Aleoshin, “Expression of hairpin-enriched mitochondrial DNA in two hairworm species (Nematomorpha)”, International Journal of Molecular Sciences, 24:14 (2023) <ext-link ext-link-type='doi' href='https://doi.org/10.3390/ijms241411411'>10.3390/ijms241411411</ext-link>

[9] L. A. Miroshnichenko, N. A. Arefeva, Yu. P. Dzhioev, V. D. Gusev, A. Yu. Borisenko, S. V. Erdyneev, Yu. S. Bukin, “Struktura povtorov v genomakh salmonell”, Matem. biologiya i bioinform, 18:2 (2023), 602–620 <ext-link ext-link-type='doi' href='https://doi.org/10.17537/2023.18.602'>10.17537/2023.18.602</ext-link>

[10] V. A. Lyubetsky, O. A. Zverkov, L. I. Rubanov, Seliverstov A. V., “Modeling RNA polymerase competition: the effect of-subunit knockout and heat shock on gene transcription level”, Biology Direct, 6:3 (2011), 1–16 <ext-link ext-link-type='doi' href='https://doi.org/10.1186/1745-6150-6-3'>10.1186/1745-6150-6-3</ext-link>

[11] O. A. Zverkov, L. Yu. Rusin, A. V. Seliverstov, V. A. Lyubetskii, “Izuchenie vstavok pryamykh povtorov v mikroevolyutsii mitokhondrii i plastid rastenii na osnove klasterizatsii belkov”, Vestnik Moskovskogo universiteta. Seriya 16. Biologiya, 2013, no. 1, 8–13

[12] Alzamel M., Hampson C., Iliopoulos C. S., Lim Z., Pissis S., Vlachakis D., Watts S., “Maximal degenerate palindromes with gaps and mismatches”, Theoretical Computer Science, 978 (2023), 1–16 <ext-link ext-link-type='doi' href='https://doi.org/10.1016/j.tcs.2023.114182'>10.1016/j.tcs.2023.114182</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=4643455'>4643455</ext-link>

[13] Needleman S. B., Wunsch Ch. D., “A general method applicable to the search for similarities in the amino acid sequence of two proteins”, Journal of Molecular Biology, 48:3 (1970), 443–453 <ext-link ext-link-type='doi' href='https://doi.org/10.1016/0022-2836(70)90057-4'>10.1016/0022-2836(70)90057-4</ext-link>

[14] V. O. Yankovskii, “Gruppy izometrii formalnykh yazykov otnositelno obobschennykh metrik Levenshteina”, Matematicheskie zametki, 116:2 (2024), 306–315 <ext-link ext-link-type='doi' href='https://doi.org/10.4213/mzm13646'>10.4213/mzm13646</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:07942210'>07942210</ext-link>

[15] M.S. Uotermen (red.), Matematicheskie metody dlya analiza posledovatelnostei DNK, Mir, M., 1999, 349 pp.

[16] Backurs A., Indyk P., “Editdistance cannot be computedinstrongly subquadratic time (unless SETH is false)”, SIAM Journal on Computing, 47:3 (2018), 1087–1097 <ext-link ext-link-type='doi' href='https://doi.org/10.1137/15M1053128'>10.1137/15M1053128</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=3818336'>3818336</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1396.68137'>1396.68137</ext-link>

[17] W. J. Masek, M. S. Paterson, “A faster algorithm computing string edit distances”, Journal of Computer and System Sciences, 20:1 (1980), 18–31 <ext-link ext-link-type='doi' href='https://doi.org/10.1016/0022-0000(80)90002-1'>10.1016/0022-0000(80)90002-1</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=566639'>566639</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:0436.68044'>0436.68044</ext-link>

[18] V. L. Arlazarov, E. A. Dinits, M. A. Kronrod, I. A. Faradzhev, “Ob ekonomnom postroenii tranzitivnogo zamykaniya orientirovannogo grafa”, Doklady AN SSSR, 194:3 (1970), 487–488 <ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=269546'>269546</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:0214.23601'>0214.23601</ext-link>

[19] M. Crochemore, G. M. Landau, M. Ziv-Ukelson, “A subquadratic sequence alignment algorithm for unrestricted score matrices”, SIAM Journal on Computing, 32:6 (2003), 1654–1673 <ext-link ext-link-type='doi' href='https://doi.org/10.1137/S0097539702402007'>10.1137/S0097539702402007</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=2034254'>2034254</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1253.74047'>1253.74047</ext-link>

[20] A. Tiskin, “Semi-local longest common subsequences in subquadratic time”, Journal of Discrete Algorithms, 6:4 (2008), 570–581 <ext-link ext-link-type='doi' href='https://doi.org/10.1016/j.jda.2008.07.001'>10.1016/j.jda.2008.07.001</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=2463421'>2463421</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1154.68543'>1154.68543</ext-link>

[21] Akmal S., Jin C., “Near-optimal quantum algorithms for string problems”, Algorithmica, 85 (2023), 2260–2317 <ext-link ext-link-type='doi' href='https://doi.org/10.1007/s00453-022-01092-x'>10.1007/s00453-022-01092-x</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=4624517'>4624517</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:07729244'>07729244</ext-link>

[22] R. K. Tetuev, M. I. Pyatkov, A. N. Pankratov, “Parallelnyi algoritm globalnogo vyravnivaniya protyazhennykh aminokislotnykh i nukleotidnykh posledovatelnostei”, Matem.biologiya i bioinform, 12:1 (2017), 137–150 <ext-link ext-link-type='doi' href='https://doi.org/10.17537/2017.12.137'>10.17537/2017.12.137</ext-link>

[23] N. Mishin, D. Berezun, A. Tiskin, “Efficient parallel algorithms for string comparison”, ICPP '21: Proceedings of the 50th International Conference on Parallel Processing, 2021, 50, 1–10 <ext-link ext-link-type='doi' href='https://doi.org/10.1145/3472456.3472489'>10.1145/3472456.3472489</ext-link>

[24] A. Tiskin, “Periodic string comparison”, Combinatorial Pattern Matching. CPM 2009, Lecture Notes in Computer Science, 5577, eds. Kucherov G., Ukkonen E., Springer, Berlin–Heidelberg, 2009 <ext-link ext-link-type='doi' href='https://doi.org/10.1007/978-3-642-02441-2'>10.1007/978-3-642-02441-2</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=2544368'>2544368</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1247.68338'>1247.68338</ext-link>

[25] B. A. Zolotov, N. S. Gaevoi, A. V. Tiskin, “Algoritmy sravneniya periodicheskikh strok”, IV Konferentsiya matematicheskikh tsentrov Rossii: sbornik tezisov (Sankt-Peterburg, 2024), 143 <ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=418200'>418200</ext-link>

[26] Sokol D., Benson G., Tojeira J., “Tandemrepeats over the edit distance”, Bioinformatics, 23:2 (2007), e30-e35 <ext-link ext-link-type='doi' href='https://doi.org/10.1093/bioinformatics/btl309'>10.1093/bioinformatics/btl309</ext-link>

[27] D. Sokol, J. Tojeira, “Speeding up the detection of tandem repeats over the edit distance”, Theoretical Computer Science, 525 (2014), 103–110 <ext-link ext-link-type='doi' href='https://doi.org/10.1016/j.tcs.2013.04.021'>10.1016/j.tcs.2013.04.021</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=3174117'>3174117</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1282.68201'>1282.68201</ext-link>

[28] A. Tiskin, “Fast distance multiplication of unit-Monge matrices”, Algorithmica, 71 (2015), 859–888 <ext-link ext-link-type='doi' href='https://doi.org/10.1007/s00453-013-9830-z'>10.1007/s00453-013-9830-z</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=3318806'>3318806</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1325.68259'>1325.68259</ext-link>

[29] A. Conte, R. Grossi, G. Punzi, T. Uno, “Enumeration of maximal common subsequences between two strings”, Algorithmica, 84 (2022), 757–783 <ext-link ext-link-type='doi' href='https://doi.org/10.1007/s00453-021-00898-5'>10.1007/s00453-021-00898-5</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=4394784'>4394784</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1518.68429'>1518.68429</ext-link>

[30] T. Kociumaka, J. Radoszewski, T. Starikovskaya, “Longest common substring with approximately k mismatches”, Algorithmica, 81:6 (2019), 2633–2652 <ext-link ext-link-type='doi' href='https://doi.org/10.1007/s00453-019-00548-x'>10.1007/s00453-019-00548-x</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=3942883'>3942883</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1412.68311'>1412.68311</ext-link>

[31] A. Amir, P. Charalampopoulos, S. P. Pissis, J. Radoszewski, “Dynamic and internal longest common substring”, Algorithmica, 82 (2020), 3707–3743 <ext-link ext-link-type='doi' href='https://doi.org/10.1007/s00453-020-00744-0'>10.1007/s00453-020-00744-0</ext-link><ext-link ext-link-type='mr-item-id' href='http://mathscinet.ams.org/mathscinet-getitem?mr=4169047'>4169047</ext-link><ext-link ext-link-type='zbl-item-id' href='https://zbmath.org/?q=an:1494.68314'>1494.68314</ext-link>

[32] J. Ai, L. H. Sun, H. Che, R. Zhang, T. Z. Zhang, W. C. Wu, X. L. Su, X. Chen, G. Yang, K. Li, Wang N., Ban T., Bao Y. N., Guo F., Niu H. F., Zhu Y. L., Zhu X. Y., Zhao S. G., B. F. Yang, “MicroRNA-195 protects against dementia induced by chronic brain hypoperfusion via its anti-amyloidogenic effect in rats”, Journal of Neuroscience, 33:9 (2013), 3989–4001 <ext-link ext-link-type='doi' href='https://doi.org/10.1523/JNEUROSCI.1997-12.2013'>10.1523/JNEUROSCI.1997-12.2013</ext-link>

[33] R. B. Chanin, P. T. West, J. Wirbel, M. O. Gill, G. Z.M. Green, R. M. Park, N. Enright, A. M. Miklos, A. S. Hickey, E. F. Brooks, K. K. Lum, I. M. Cristea, A. S. Bhatt, “Intragenic DNAinversions expand bacterial coding capacity”, Nature, 634 (2024), 234–242 <ext-link ext-link-type='doi' href='https://doi.org/10.1038/s41586-024-07970-4'>10.1038/s41586-024-07970-4</ext-link>