Abstract
Strings are widely used to describe and store information in bioinformatics, such as DNA and proteins. The determination of a consensus for a string profile plays an important role in bioinformatics. There are several postulates to determine consensus, among which postulate 1-Optimality is the most popular. A consensus that satisfies this postulate is the best representative of the profile. Another essential postulate is 2-Optimality. A consensus satisfying postulate 2-Optimality is the best representative, and the distances between it and the profile members are more uniform than those satisfying the postulate 1-Optimality. However, the determination of the 2-Optimality consensus has not been examined in bioinformatics because of its complexity. It is meaningful to investigate this type of consensus. Thus, this study focuses on formulating and proposing algorithms to determine the 2-Optimality consensus for DNA motif profiles.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Pradhan, M. : Motif Discovery in Biological Sequences. San Jose State University, San Jose, CA, USA (2008)
Compeau, P., Pevzner, P.: Bioinformatics algorithms: an active learning approach. United States of America (2015)
D’haeseleer, P.: What are DNA sequence motifs? Nat. Biotechnol. 24(4), 423–425 (2006)
Gribskov, M.: Identification of sequence patterns, motifs and domains. Encycl. Bioinforma. Comput. Biol. ABC Bioinforma. 1–3, 332–340 (2018)
Blum, C., Festa, P.: Metaheuristics for String Problems in Bio-informatics, vol. 6. Wiley, Hoboken (2016)
Nguyen, N.T.: Advanced Methods for Inconsistent Knowledge Management. Springer, London (2008). https://doi.org/10.1007/978-1-84628-889-0
Nguyen, N.T.: Inconsistency of knowledge and collective intelligence. Cybern. Syst. 39(6), 542–562 (2008)
Nguyen, N.T.: Using distance functions to solve representation choice problems. Fundam. Inf. 48, 295–314 (2001)
Nguyen, N.T.: Processing inconsistency of knowledge in determining knowledge of a collective. Cybern. Syst. 40(8), 670–688 (2009)
Dang, D.T., Nguyen, N.T., Hwang, D.: Multi-step consensus: an effective approach for determining consensus in large collectives. Cybern. Syst. 50(2), 208–229 (2019)
Amir, A., Landau, G.M., Na, J.C., Park, H., Park, K., Sim, J.S.: Efficient algorithms for consensus string problems minimizing both distance sum and radius. Theor. Comput. Sci. 412(39), 5239–5246 (2011)
Hashim, F.A., Mabrouk, M.S., Al-Atabany, W.: Review of different sequence motif finding algorithms. Avicenna J. Med. Biotechnol. 11(2), 130–148 (2019)
Sinha, S.: YMF: a program for discovery of novel transcription factor binding sites by statistical overrepresentation. Nucleic Acids Res. 31(13), 3586–3588 (2003)
Sinha, S.: Discovery of novel transcription factor binding sites by statistical overrepresentation. Nucleic Acids Res. 30(24), 5549–5560 (2002)
Sharov, A.A., Ko, M.S.H.: Exhaustive search for over-represented DNA sequence motifs with cisfinder. DNA Res. 16(5), 261–273 (2009)
Zare-Mirakabad, F., Ahrabian, H., Sadeghi, M., Hashemifar, S., Nowzari-Dalini, A., Goliaei, B.: Genetic algorithm for dyad pattern finding in DNA sequences. Genes Genet. Syst. 84(1), 81–93 (2009)
Bouamama, S., Boukerram, A., Al-Badarneh, A.F.: Motif finding using ant colony optimization. In: Dorigo, M., et al. (eds.) ANTS 2010. LNCS, vol. 6234, pp. 464–471. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-15461-4_45
Bailey, T.L., Williams, N., Misleh, C., Li, W.W.: MEME: discovering and analyzing DNA and protein sequence motifs. Nucleic Acids Res. 34, 369–373 (2006)
Das, M.K., Dai, H.K.: A survey of DNA motif finding algorithms. BMC Bioinf. 8, 1–13 (2007)
Amir, A., Landau, G.M., Na, J.C., Park, H., Park, K., Sim, J.S.: Consensus optimizing both distance sum and radius. In: Karlgren, J., Tarhio, J., Hyyrö, H. (eds.) SPIRE 2009. LNCS, vol. 5721, pp. 234–242. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-03784-9_23
Lin, F.-T., Kao, C.-Y., Hsu, C.-C.: Applying the genetic approach to simulated annealing in solving some NP-hard problems. IEEE Trans. Syst. Man. Cybern. 23(6), 1752–1767 (1993)
Dang, D.T., Nguyen, N.T., Hwang, D.: A quick algorithm to determine 2-optimality consensus for collectives. IEEE Access 8, 221794–221807 (2020)
Michiels, W., Aarts, E.H.L., Korst, J.: Theory of local search. In: Martí, R., Pardalos, P., Resende, M. (eds.) Handbook of Heuristics, vol. 1–2, pp. 299–339. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-07124-4_6
Benito-Parejo, M., Merayo, M.G., Nunez, M. : An evolutionary technique for supporting the consensus process of group decision making. In: 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pp. 2201–2206 (2020)
Katoch, S., Chauhan, S.S., Kumar, V.: A review on genetic algorithm: past, present, and future. Multimed. Tools Appl. 80(5), 8091–8126 (2020). https://doi.org/10.1007/s11042-020-10139-6
Dang, D.C., et al.: Escaping local optima using crossover with emergent diversity. IEEE Trans. Evol. Comput. 22(3), 484–497 (2018)
Schnecke, V., Vornberger, O., Schnecke, V.: Hybrid genetic algorithms for constrained placement problems. IEEE Trans. Evol. Comput. 1(4), 266–271 (1997)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 Springer Nature Switzerland AG
About this paper
Cite this paper
Dang, D.T., Phan, H.T., Nguyen, N.T., Hwang, D. (2021). Determining 2-Optimality Consensus for DNA Structure. In: Fujita, H., Selamat, A., Lin, J.CW., Ali, M. (eds) Advances and Trends in Artificial Intelligence. Artificial Intelligence Practices. IEA/AIE 2021. Lecture Notes in Computer Science(), vol 12798. Springer, Cham. https://doi.org/10.1007/978-3-030-79457-6_36
Download citation
DOI: https://doi.org/10.1007/978-3-030-79457-6_36
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-79456-9
Online ISBN: 978-3-030-79457-6
eBook Packages: Computer ScienceComputer Science (R0)