{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,2]],"date-time":"2025-08-02T17:54:18Z","timestamp":1754157258545,"version":"3.41.2"},"reference-count":59,"publisher":"Emerald","issue":"1","license":[{"start":{"date-parts":[[2008,3,28]],"date-time":"2008-03-28T00:00:00Z","timestamp":1206662400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.emerald.com\/insight\/site-policies"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008,3,28]]},"abstract":"<jats:sec><jats:title content-type=\"abstract-heading\">Purpose<\/jats:title><jats:p>Multiple sequence alignment (MSA) is one of essential bioinformatics methods for decoding cis\u2010regulatory elements in gene regulation, predicting structure and function of proteins and RNAs, reconstructing phylogenetic tree, and other common tasks in biomolecular sequence analysis. The purpose of this paper is to describe briefly the basic concepts and formulations of gapped MSA and un\u2010gapped motif discovery approaches, and then review computational intelligence (CI) applications in MSA and motif\u2010finding problems.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Design\/methodology\/approach<\/jats:title><jats:p>This paper performs exhaustive literature review on the MSA and motif discovery using CI techniques.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Findings<\/jats:title><jats:p>Although CI\u2010based MSA algorithms were developed nearly a decade ago, most recent CI effort seems attempted to tackle the NP\u2010complete motif discovery problem. Applications of various CI techniques to solve motif discovery problem, including neural networks, self\u2010organizing map, genetic algorithms, swarm intelligence and combinations thereof, are surveyed. Finally, the paper concludes with discussion and perspective.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Practical implications<\/jats:title><jats:p>The algorithms and software discussed in this paper can be used to align DNA, RNA and protein sequences, discover motifs, predict functions and structures of protein and RNA sequences, and estimate phylogenetic tree.<\/jats:p><\/jats:sec><jats:sec><jats:title content-type=\"abstract-heading\">Originality\/value<\/jats:title><jats:p>The paper contributes to the first comprehensive survey of CI techniques that are applied to MSA and motif discovery.<\/jats:p><\/jats:sec>","DOI":"10.1108\/17563780810857103","type":"journal-article","created":{"date-parts":[[2008,4,12]],"date-time":"2008-04-12T07:14:15Z","timestamp":1207984455000},"page":"8-24","source":"Crossref","is-referenced-by-count":4,"title":["Computational intelligence in multiple sequence alignment"],"prefix":"10.1108","volume":"1","author":[{"given":"Chengpeng","family":"Bi","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"140","reference":[{"key":"key2022012820060430200_b1","unstructured":"Anabarasu, L.A. (1998), \u201cMultiple sequence alignment using parallel genetic algorithms\u201d, paper presented at the 2nd Asia\u2010Pacific Conference on Simulated Evolution (SEAL\u201098), Canberra."},{"key":"key2022012820060430200_b2","doi-asserted-by":"crossref","unstructured":"Back, T. (1996), Evolutionary Algorithms in Theory and Practice, Oxford University Press, New York, NY.","DOI":"10.1093\/oso\/9780195099713.003.0007"},{"key":"key2022012820060430200_b3","doi-asserted-by":"crossref","unstructured":"Baker, D. and Sali, A. (2001), \u201cProtein structure prediction and structural genomics\u201d, Science, Vol. 294, pp. 93\u20106.","DOI":"10.1126\/science.1065659"},{"key":"key2022012820060430200_b5","doi-asserted-by":"crossref","unstructured":"Bi, C\u2010P. (2007a), \u201cSEAM: A stochastic EM\u2010type algorithm for motif\u2010finding in biopolymer sequences\u201d, J. Bioinformatics and Comput. Biol., Vol. 5, pp. 47\u201077.","DOI":"10.1142\/S0219720007002527"},{"key":"key2022012820060430200_b6","doi-asserted-by":"crossref","unstructured":"Bi, C\u2010P. (2007b), \u201cA genetic\u2010based EM motif\u2010finding algorithm for biological sequence analysis\u201d, Proc. IEEE Symposium on Computat. Intelligence in Bioinformatics and Computat. Biol., Vol. 7, pp. 275\u201082.","DOI":"10.1109\/CIBCB.2007.4221233"},{"key":"key2022012820060430200_b7","unstructured":"Bi, C\u2010P. (2007c), \u201cA survey of in silico motif discovery and computational intelligence applications\u201d, Proceedings of International Conference on Artificial Intelligence, CSREA Press, pp. 147\u201053."},{"key":"key2022012820060430200_b8","doi-asserted-by":"crossref","unstructured":"Bi, C\u2010P. (2007d), \u201cData augmentation algorithms for detecting conserved domains in protein sequences: a comparative study\u201d, Journal of Proteome Res., December 15.","DOI":"10.1021\/pr070475q"},{"key":"key2022012820060430200_b9","doi-asserted-by":"crossref","unstructured":"Bi, C\u2010P., Leeder, J.S. and Vyhlidal, C.A. (2007), \u201cA comparative study on computational two\u2010block motif detection: algorithms and applications\u201d, Molecular Pharmaceutics, December 13.","DOI":"10.1021\/mp7001126"},{"key":"key2022012820060430200_b10","doi-asserted-by":"crossref","unstructured":"Bonizzoni, P. and Vedova, G.D. (2001), \u201cThe complexity of multiple sequence alignment with SP\u2010score that is a metric\u201d, Theoretical Computer Science, Vol. 259, pp. 63\u201079.","DOI":"10.1016\/S0304-3975(99)00324-2"},{"key":"key2022012820060430200_b11","doi-asserted-by":"crossref","unstructured":"Che, D. et al. (2005), \u201cMDGA: motif discovery using a genetic algorithm\u201d, Proc. GECCO, USA, Vol. 5, pp. 447\u201052.","DOI":"10.1145\/1068009.1068080"},{"key":"key2022012820060430200_b12","unstructured":"Chellapilla, K. and Fogel, G.B. (1999), \u201cMultiple sequence alignment using evolutionary programming\u201d, Proceedings of the First Congress of Evolutionary Computation (CEC\u20101999), pp. 445\u201052."},{"key":"key2022012820060430200_b13","unstructured":"Davis, L. (1989), \u201cAdapting operator probabilities in genetic algorithms\u201d, Proceedings of the Third International Conference on Genetic Algorithms (ICGA III), pp. 61\u20109."},{"key":"key2022012820060430200_b14","doi-asserted-by":"crossref","unstructured":"Dorigo, M. and Gambardella, L.M. (1997), \u201cAnt colony system: a cooperative learning approach to the traveling salesman problem\u201d, IEEE Transaction on Evolution Computation, Vol. 1, pp. 55\u201066.","DOI":"10.1109\/4235.585892"},{"key":"key2022012820060430200_b15","doi-asserted-by":"crossref","unstructured":"Dorigo, M., Di Caro, G. and Gambardella, L.M. (1999), \u201cAnt algorithms for discrete optimization\u201d, Artificial Life, Vol. 5, pp. 137\u201072.","DOI":"10.1162\/106454699568728"},{"key":"key2022012820060430200_b16","doi-asserted-by":"crossref","unstructured":"Edgar, R.C. and Batzoglou, S. (2006), \u201cMultiple sequence alignment\u201d, Current Opinion in Structural Biology, Vol. 16, pp. 368\u201073.","DOI":"10.1016\/j.sbi.2006.04.004"},{"key":"key2022012820060430200_b48","doi-asserted-by":"crossref","unstructured":"The ENCODE Project Consortium (2007), \u201cIdentification and analysis of functional elements in 1% of the human genome by the ENCODE pilot project\u201d, Science, Vol. 447, pp. 799\u2010816.","DOI":"10.1038\/nature05874"},{"key":"key2022012820060430200_b17","doi-asserted-by":"crossref","unstructured":"Feng, D. and Doolittle, R. (1987), \u201cProgressive sequence alignment as a prerequisite to correct phylogenetic trees\u201d, Journal of Molecular Evolution, Vol. 25, pp. 351\u201060.","DOI":"10.1007\/BF02603120"},{"key":"key2022012820060430200_b19","doi-asserted-by":"crossref","unstructured":"Fogel, G.B., Weekes, D.G., Varga, G., Dow, E.R., Harlow, H.B., Onyia, J.E. and Su, C. (2004), \u201cDiscovery of sequence motifs related to co\u2010expression of genes using evolutionary computation\u201d, Nucleic Acids Res., Vol. 32, pp. 3826\u201035.","DOI":"10.1093\/nar\/gkh713"},{"key":"key2022012820060430200_b18","unstructured":"Fogel, L.J. (1991), System Identification Through Simulated Evolution: A Machine Learning Approach to Modeling, Ginn Press, Needham Heights, MA."},{"key":"key2022012820060430200_b20","unstructured":"Holland, J.H. (1975), Adaptation in Natural and Artificial Asystems, MIT Press, Cambridge, MA."},{"key":"key2022012820060430200_b21","unstructured":"Kennedy, J. and Eberhart, R.C. (2001), Swarm Intelligence, Morgan Kaufmann Publishers, San Fransisco, CA."},{"key":"key2022012820060430200_b22","doi-asserted-by":"crossref","unstructured":"Kim, J., Pramanik, S. and Chung, M. (1994), \u201cMultiple sequence alignment using simulated annealing\u201d, Computer Applications in the Biosciences (CABIOS), Vol. 10, pp. 419\u201026.","DOI":"10.1093\/bioinformatics\/10.4.419"},{"key":"key2022012820060430200_b23","doi-asserted-by":"crossref","unstructured":"Larsen, J.N., Engelbrecht, I. and Brunak, S. (1995), \u201cAnalysis of eukaryotic promoter sequences reveals a systematically occurring CT\u2010signal\u201d, Nucleic Acids Research, Vol. 23, pp. 1223\u201030.","DOI":"10.1093\/nar\/23.7.1223"},{"key":"key2022012820060430200_b24","doi-asserted-by":"crossref","unstructured":"Lawrence, C.E. and Reilly, A.A. (1990), \u201cAn expectation maximization algorithm for the identification and characterization of common sites in unaligned biopolymer sequences\u201d, Proteins: Structure, Function and Genetics, Vol. 7, pp. 41\u201051.","DOI":"10.1002\/prot.340070105"},{"key":"key2022012820060430200_b26","doi-asserted-by":"crossref","unstructured":"Li, L., Liang, Y. and Bass, R.L. (2007), \u201cGAPWM: a genetic algorithm method for optimizing a position weight matrix\u201d, Bioinformatics, Vol. 23, pp. 1188\u201094.","DOI":"10.1093\/bioinformatics\/btm080"},{"key":"key2022012820060430200_b27","doi-asserted-by":"crossref","unstructured":"Liu, D., Xiong, X., DasGupta, B. and Zhang, H. (2006), \u201cMotif discoveries in unaligned molecular sequences using self\u2010organizing neural networks\u201d, IEEE Trans. Neural Networks, Vol. 17, pp. 919\u201028.","DOI":"10.1109\/TNN.2006.875987"},{"key":"key2022012820060430200_b28","unstructured":"Liu, F.F.M., Tsai, J.J.P., Chen, R.M., Chen, S.N. and Shih, S.H. (2005), \u201cFMGA: finding motifs by genetic algorithm\u201d, BIBE, Vol. 4, p. 459."},{"key":"key2022012820060430200_b29","unstructured":"Liu, J.S. (2001), Monte Carlo Strategies for Scientific Computing, Springer\u2010Verlag, New York, NY."},{"key":"key2022012820060430200_b31","unstructured":"Liu, Y. and Yokota, H. (2005), \u201cModeling transcriptional regulation in chondrogenesis using particle swarm optimization\u201d, Proceeding of the CIBCB 2005."},{"key":"key2022012820060430200_b30","doi-asserted-by":"crossref","unstructured":"Liu, Y. and Yokota, H. (2006), \u201cArtificial ants deposit pheromone to search for regulatory DNA elements\u201d, BMC Genomics, Vol. 7, p. 221.","DOI":"10.1186\/1471-2164-7-221"},{"key":"key2022012820060430200_b32","doi-asserted-by":"crossref","unstructured":"Lones, M.A. and Tyrrell, A.M. (2007), \u201cRegulatory motif discovery using a population clustering evolutionary algorithm\u201d, IEEE\/ACM Trans. Computat. Biol. Bioinformatics, Vol. 4, pp. 403\u201014.","DOI":"10.1109\/tcbb.2007.1044"},{"key":"key2022012820060430200_b33","doi-asserted-by":"crossref","unstructured":"MacIsaac, K.D. and Fraenkel, E. (2006), \u201cPractical strategies for discovering regulatory DNA sequence motifs\u201d, PLoS Comput. Biol., Vol. 2, p. e36.","DOI":"10.1371\/journal.pcbi.0020036"},{"key":"key2022012820060430200_b34","doi-asserted-by":"crossref","unstructured":"Mahony, S., Hendrix, D., Golden, A., Smith, T.J. and Rokhsar, D.S. (2005), \u201cTranscription factor binding site identification using the self\u2010organizing map\u201d, Bioinformatics, Vol. 21, pp. 1807\u201014.","DOI":"10.1093\/bioinformatics\/bti256"},{"key":"key2022012820060430200_b35","doi-asserted-by":"crossref","unstructured":"NC\u2010IUB (1986), \u201cNomenclature for incompletely specified bases in nucleic acid sequences \u2013 recommendations 1984\u201d, Proc. Natl. Acad. Sci., USA, Vol. 83, pp. 4\u20108.","DOI":"10.1073\/pnas.83.1.4"},{"key":"key2022012820060430200_b36","doi-asserted-by":"crossref","unstructured":"Notredame, C. (2002), \u201cRecent progresses in multiple sequence alignment: a survey\u201d, Pharmacogenomics, Vol. 3, pp. 1\u201014.","DOI":"10.1517\/14622416.3.1.131"},{"key":"key2022012820060430200_b40","doi-asserted-by":"crossref","unstructured":"Notredame, C. (2007), \u201cRecent evolutions of multiple sequence alignment algorithms\u201d, PLoS Computational Biology, Vol. 3, p. e123.","DOI":"10.1371\/journal.pcbi.0030123"},{"key":"key2022012820060430200_b37","doi-asserted-by":"crossref","unstructured":"Notredame, C. and Higgins, D.G. (1996), \u201cSAGA: sequence alignment by genetic algorithm\u201d, Nucleic Acids Res., Vol. 24, pp. 1515\u201042.","DOI":"10.1093\/nar\/24.8.1515"},{"key":"key2022012820060430200_b38","doi-asserted-by":"crossref","unstructured":"Notredame, C., O'Brien, E.A. and Higgins, D.G. (1997), \u201cRAGA: RNA sequence alignment by genetic algorithm\u201d, Nucleic Acids Res., Vol. 25, pp. 4570\u201080.","DOI":"10.1093\/nar\/25.22.4570"},{"key":"key2022012820060430200_b39","doi-asserted-by":"crossref","unstructured":"Notredame, C., Holm, L. and Higgins, D.G. (1998), \u201cCOFFEE: an objective function for multiple sequence alignments\u201d, Bioinformatics, Vol. 14, pp. 407\u201022.","DOI":"10.1093\/bioinformatics\/14.5.407"},{"key":"key2022012820060430200_b41","doi-asserted-by":"crossref","unstructured":"ONeil, M.C. (1992), \u201cEscherichia coli promoters: neural networks develop distinct descriptions in learning to search for promoters of different spacing classes\u201d, Nucleic Acids Research, Vol. 20, pp. 3471\u20107.","DOI":"10.1093\/nar\/20.13.3471"},{"key":"key2022012820060430200_b42","doi-asserted-by":"crossref","unstructured":"Optitz, D.W. and Shavlik, J.W. (1997), \u201cConnectionist theory refinement: genetically searching the space of network topologies\u201d, J. Artificial Intelligence Res., Vol. 6, pp. 177\u2010209.","DOI":"10.1613\/jair.368"},{"key":"key2022012820060430200_b43","doi-asserted-by":"crossref","unstructured":"Phillips, A., Janies, D. and Wheeler, W. (2000), \u201cMultiple sequence alignment in phylogenetic analysis\u201d, Mol. Phylogenetics and Evolution, Vol. 16, pp. 317\u201030.","DOI":"10.1006\/mpev.2000.0785"},{"key":"key2022012820060430200_b44","unstructured":"Rosenblatt, F. (1962), Principles of Neurodynamics, Spartan Books, Washington, DC."},{"key":"key2022012820060430200_b45","unstructured":"Stine, M., Dasgupta, D. and Mukatira, S. (2003), \u201cMotif discovery in upstream sequences of coordinately expressed genes\u201d, Proc. CEC\u201003, Vol. 3, pp. 1596\u2010603."},{"key":"key2022012820060430200_b47","doi-asserted-by":"crossref","unstructured":"Stormo, G.D. (2000), \u201cDNA binding sites: representation and discovery\u201d, Bioinformatics, Vol. 16, pp. 16\u201023.","DOI":"10.1093\/bioinformatics\/16.1.16"},{"key":"key2022012820060430200_b46","doi-asserted-by":"crossref","unstructured":"Stormo, G.D. et al., (1982), \u201cUse of the perceptron algorithm to distinguish translation initiation sites in E. coli\u201d, Nucleic Acids Research, Vol. 10, pp. 2997\u20103011.","DOI":"10.1093\/nar\/10.9.2997"},{"key":"key2022012820060430200_b49","doi-asserted-by":"crossref","unstructured":"Thompson, J., Higgins, D. and Gibson, T. (1994), \u201cClustal W: improving the sensitivity of progressive multiple sequence alignment through sequence weighting\u201d, Nucleic Acids Research, Vol. 22, pp. 4673\u201080.","DOI":"10.1093\/nar\/22.22.4673"},{"key":"key2022012820060430200_b50","unstructured":"Thomsen, R., Fogel, G. and Krink, T. (2003), \u201cImprovement of Clustal\u2010derived sequence alignments with evolutionary algorithms\u201d, Proceedings of the Fifth Congress on Evolutionary Computation (CEC\u20102003), pp. 121\u20106."},{"key":"key2022012820060430200_b51","unstructured":"Tompa, M. et al., (2005), \u201cAssessing computational tools for the discovery of transcription factor binding sites\u201d, Nature Biotechnology, Vol. 23, pp. 137\u201044."},{"key":"key2022012820060430200_b52","unstructured":"Tsoukalas, L.H. and Uhrig, R.E. (1997), Fuzzy and Neural Approaches in Engineering, Wiley, New York, NY."},{"key":"key2022012820060430200_b53","doi-asserted-by":"crossref","unstructured":"Wang, L. and Jiang, T. (1994), \u201cOn the complexity of multiple sequence alignment\u201d, Journal of Computational Biology, Vol. 1, pp. 337\u201048.","DOI":"10.1089\/cmb.1994.1.337"},{"key":"key2022012820060430200_b54","doi-asserted-by":"crossref","unstructured":"Waterman, M. (1995), Introduction to Computational Biology, CRC, New York, NY.","DOI":"10.1007\/978-1-4899-6846-3"},{"key":"key2022012820060430200_b55","doi-asserted-by":"crossref","unstructured":"Wei, Z. and Jensen, S.T. (2006), \u201cGAME: detecting cis\u2010regulatory elements using genetic algorithm\u201d, Bioinformatics, Vol. 22, pp. 1577\u201084.","DOI":"10.1093\/bioinformatics\/btl147"},{"key":"key2022012820060430200_b57","doi-asserted-by":"crossref","unstructured":"Zhang, C. and Wong, A.K. (1997), \u201cA genetic algorithm for multiple molecular sequence alignment\u201d, Comput. Appl. Biosci., Vol. 13, pp. 565\u201081.","DOI":"10.1093\/bioinformatics\/13.6.565"},{"key":"key2022012820060430200_b58","doi-asserted-by":"crossref","unstructured":"Zhang, M.Q. (2002), \u201cComputational prediction of eukaryotic protein\u2010coding genes\u201d, Nature Reviews Genetics, Vol. 3, pp. 698\u2010709.","DOI":"10.1038\/nrg890"},{"key":"key2022012820060430200_b59","doi-asserted-by":"crossref","unstructured":"Zhou, Q. and Wong, W.H. (2004), \u201cCisModule: de novo discovery of cis\u2010regulatory modules by hierarchical mixture modeling\u201d, Proc. Natl. Acad. Sci., USA, Vol. 101, pp. 12114\u20109.","DOI":"10.1073\/pnas.0402858101"},{"key":"key2022012820060430200_frd1","doi-asserted-by":"crossref","unstructured":"Berg, O.G. and von Hippel, P.H. (1987), \u201cSelection of DNA binding sites by regulatory proteins: statistical\u2010mechanical theory and application to operators and promoters\u201d, Journal of Molecular Biology, Vol. 193, pp. 723\u201050.","DOI":"10.1016\/0022-2836(87)90354-8"},{"key":"key2022012820060430200_frd2","doi-asserted-by":"crossref","unstructured":"Lawrence, C.E., Altschul, S., Boguski, M., Liu, J.S., Neuwald, A. and Wootton, J. (1993), \u201cDetecting subtle sequence signals: a Gibbs sampling strategy for multiple alignment\u201d, Science, Vol. 262, pp. 208\u201014.","DOI":"10.1126\/science.8211139"},{"key":"key2022012820060430200_frd3","doi-asserted-by":"crossref","unstructured":"Wootton, J.C. and Federhen, S. (1996), \u201cAnalysis of compositionally biased regions in sequence databases\u201d, Methods Enzymol., Vol. 266, pp. 554\u201071.","DOI":"10.1016\/S0076-6879(96)66035-2"}],"container-title":["International Journal of Intelligent Computing and Cybernetics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/www.emeraldinsight.com\/doi\/full-xml\/10.1108\/17563780810857103","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17563780810857103\/full\/xml","content-type":"application\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/www.emerald.com\/insight\/content\/doi\/10.1108\/17563780810857103\/full\/html","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,24]],"date-time":"2025-07-24T23:44:09Z","timestamp":1753400649000},"score":1,"resource":{"primary":{"URL":"http:\/\/www.emerald.com\/ijicc\/article\/1\/1\/8-24\/130299"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,3,28]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,3,28]]}},"alternative-id":["10.1108\/17563780810857103"],"URL":"https:\/\/doi.org\/10.1108\/17563780810857103","relation":{},"ISSN":["1756-378X"],"issn-type":[{"type":"print","value":"1756-378X"}],"subject":[],"published":{"date-parts":[[2008,3,28]]}}}