Efficient automatic exact motif discovery algorithms for biological sequences |
| |
| Authors: | Ali Karci |
| |
| Affiliation: | 1. Tampere Center for Child Health Research, University of Tampere and Tampere University Hospital, Tampere, Finland;2. Institute of Biomedicine, School of Medicine, University of Eastern Finland, Kuopio, Finland;3. Institute of Biosciences and Medical Technology, University of Tampere, Finland;4. Department of Signal Processing, Tampere University of Technology, Tampere, Finland;1. Metabolomics Platform – IISPV, Department of Electrical and Automation Engineering (DEEEA), Universitat Rovira i Virgili, Tarragona, Catalonia, Spain;2. Biomedical Research Centre in Diabetes and Associated Metabolic Disorders (CIBERDEM), Madrid, Spain;3. B2SLAB, Department of ESAII – Center for Biomedical Engineering Research (CREB), Universitat Politècnica de Catalunya, Barcelona, Catalonia, Spain;4. Biomedical Research Centre in Bioengineering, Biomaterials and Nanomedicine (CIBERBBN), Madrid, Spain;1. Department of Information Management, National University of Kaohsiung, 700 Kaohsiung University Rd., Nanzih District, Kaohsiung 811, Taiwan;2. Department of Information Management, Kun Shan University, 949 Dawan Rd., Yung-Kung District, Tainan 71003, Taiwan;3. Graduate School of Information Science and Technology, Osaka University, 1-1 Yamadaoka, Suita, Osaka 565-0871, Japan;1. Department of Process Engineering, University of Stellenbosch, Private Bag X1, Stellenbosch 7602, South Africa;2. Department of Microbiology, University of Stellenbosch, Private Bag X1, Stellenbosch 7602, South Africa |
| |
| Abstract: | ObjectiveThis paper presents an algorithm for the solution of the motif discovery problem (MDP).Methods and materialsMotif discovery problem can be considered in two cases: motifs with insertions/deletions, and motifs without insertions/deletions. The first group motifs can be found by stochastic and approximated methods. The second group can be found by using stochastic and approximated methods, but also deterministic method. We proved that the second group motifs can be found with a deterministic algorithm, and so, it can be said that the second motifs finding is a P-type problem as proved in this paper.Results and conclusionsAn algorithm was proposed in this paper for motif discovery problem. The proposed algorithm finds all motifs which are occurred in the sequence at least two times, and it also finds motifs of various sizes. Due to this case, this algorithm is regarded as Automatic Exact Motif Discovery Algorithm. All motifs of different sizes can be found with this algorithm, and this case was proven in this paper. It shown that automatic exact motif discovery is a P-type problem in this paper. The application of the proposed algorithm has been shown that this algorithm is superior to MEME, MEME3, Motif Sampler, WEEDER, CONSENSUS, AlignACE. |
| |
| Keywords: | Motif discovery Computational biology DNA Biological sequences Algorithms Bioinformatics |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
