An Efficient Exact Algorithm for Planted Motif Search on Large DNA Sequence Datasets
IEEE/ACM Transactions on Computational Biology and Bioinformatics · 2024
DOI: 10.1109/tcbb.2024.3404136 ↗Kurz gefasst
Fachartikel in der Zeitschrift IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2024. Verfasst von Qiang Yu und 4 weiteren Autor:innen. Hauptthemen laut MEDLINE: Algorithms, Nucleotide Motifs, Sequence Analysis, DNA, Computational Biology. Die Arbeit wurde bisher 1-mal zitiert (Crossref) und nennt 33 Literaturangaben. Gefördert von: Natural Science Basic Research Program of Shaanxi.
Abstract (Originalsprache)
DNA motif is the pattern shared by similar fragments in DNA sequences, which plays a key role in regulating gene expression, and DNA motif discovery has become a key research topic. Exact planted ( l, d )-motif search (PMS) is one of the motif discovery approaches, which aims to find from t sequences all the ( l, d )-motifs that are motifs of l length appearing in at least qt sequences with at most d mismatches. The existing exact PMS algorithms are only suitable for small datasets of DNA sequences. The development of high-throughput sequencing technology generates vast amount of DNA sequence data, which brings challenges to solving exact PMS problems efficiently. Therefore, we propose an efficient exact PMS algorithm called PMmotif for large datasets of DNA sequences, after analyzing the time complexity of the existing exact PMS algorithms. PMmotif finds ( l, d )-motifs with strategy by searching the branches on the pattern tree that may contain ( l, d )-motifs. It is verified by experiments that the running time ratio of some existing excellent PMS algorithms to PMmotif is between 14.83 and 58.94. In addition, for the first time, PMmotif can solve the ( 15,5 )and ( 17,6 ) challenge problem instances on large DNA sequence datasets (3000 sequences of length 200) within 24 hours.
Schlagwörter
MeSH-Schlagwörter (MEDLINE)
Substanzen
Förderung
- Natural Science Basic Research Program of Shaanxi
Zitieren
APA
Yu, Q., Hu, Y., Hu, X., Lan, J., & Guo, Y. (2024). An Efficient Exact Algorithm for Planted Motif Search on Large DNA Sequence Datasets. IEEE/ACM Transactions on Computational Biology and Bioinformatics. https://doi.org/10.1109/tcbb.2024.3404136
Vancouver
Yu Q, Hu Y, Hu X, Lan J, Guo Y. An Efficient Exact Algorithm for Planted Motif Search on Large DNA Sequence Datasets. IEEE/ACM Transactions on Computational Biology and Bioinformatics. 2024. doi:10.1109/tcbb.2024.3404136
BibTeX
@article{Yu2024,
author = {Yu, Qiang and Hu, Yana and Hu, Xinnan and Lan, Jingfen and Guo, Yang},
title = {An Efficient Exact Algorithm for Planted Motif Search on Large DNA Sequence Datasets},
journal = {IEEE/ACM Transactions on Computational Biology and Bioinformatics},
year = {2024},
doi = {10.1109/tcbb.2024.3404136}
}
EUVIMED