Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Thuật Toán Chính Xác Hiệu Suất Cao Để Tìm Kiếm Động Học
Tóm tắt
Mục tiêu. Dự án gen người đã tạo ra một lượng lớn dữ liệu sinh học. Cần có những kỹ thuật tính toán mới để trích xuất thông tin hữu ích từ các dữ liệu này. Một trong những kỹ thuật như vậy là tìm các mẫu được lặp lại qua nhiều chuỗi (và có thể qua nhiều loài). Trong bài báo này, chúng tôi nghiên cứu vấn đề xác định các mẫu có nghĩa (tức là, motif) từ dữ liệu sinh học, vấn đề tìm kiếm motif. Phương pháp. Phiên bản chung của vấn đề tìm kiếm motif là NP-khó. Nhiều thuật toán đã được đề xuất trong tài liệu để giải quyết vấn đề này. Nhiều thuật toán trong số này thuộc thể loại đánh lừa. Chúng tôi tập trung vào các thuật toán chính xác trong bài báo này. Cụ thể, chúng tôi tập trung vào hai phiên bản khác nhau của vấn đề tìm kiếm motif và đưa ra các thuật toán chính xác cho chúng. Kết quả. Trong bài báo này, chúng tôi trình bày các thuật toán cho hai phiên bản của vấn đề tìm kiếm motif. Tất cả các thuật toán của chúng tôi đều thanh lịch và chỉ sử dụng những cấu trúc dữ liệu đơn giản như mảng. Đối với phiên bản đầu tiên của vấn đề được mô tả là Vấn đề 1 trong bài báo, chúng tôi trình bày một thuật toán dựa trên sắp xếp đơn giản, SMS (Tìm Kiếm Motif Đơn Giản). Thuật toán này đã được lập trình và các kết quả thử nghiệm đã được thu thập. Đối với phiên bản thứ hai của vấn đề (được mô tả trong bài báo là Vấn đề 2), chúng tôi trình bày hai thuật toán khác nhau – một thuật toán xác định (gọi là DMS) và một thuật toán ngẫu nhiên (thuật toán Monte Carlo). Chúng tôi cũng chỉ ra cách các thuật toán này có thể được song song hóa. Kết luận. Tất cả các thuật toán được đề xuất trong bài báo này đều là sự cải tiến so với các thuật toán hiện có cho các phiên bản tìm kiếm motif này trong dữ liệu chuỗi sinh học. Các thuật toán được trình bày có tiềm năng hoạt động tốt trong thực tế.
Từ khóa
#dữ liệu sinh học #tìm kiếm motif #thuật toán chính xác #NP-khó #chuỗi sinh họcTài liệu tham khảo
Adebiyi EF, Jiang T, Kaufmann M. An efficient algorithm for finding short approximate non-tandem repeats. Bioinformatics 2001; 17(1): S5–S12.
Adebiyi EF, Kaufmann M. Extracting common motifs under the Levenshtein measure: Theory and experimentation, Proc. Workshop on Algorithms for Bioinformatics (WABI). Springer-Verlag LNCS 2002; 2452: 140–156.
Buhler J, Tompa M. Finding motifs using random projections, Proc. Fifth Annual International Conference on Computational Molecular Biology (RECOMB) 2001.
Chernoff H. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Annals of Math Statistics 1952; 23: 493–507.
Floratos A, Rigoutsos I. On the Time Complexity of the TEIRESIAS Algorithm, Research Report RC 21161 (94582), IBM TJ, Watson Research Center 1998.
Galil Z, Park K. An improved algorithm for approximate string matching. SIAM Journal of Computing 1990; 19(6): 989–999.
Horowitz E, Sahni S, Rajasekaran S. Computer Algorithms. W. H. Freeman Press, 1998.
Landau GM, Vishkin U. Introducing efficient parallelism into approximate string matching and a new serial algorithm, Proc. ACM Symposium on Theory of Computing 1986: 220–230.
Martinez HM. An efficient method for finding repeats in molecular sequences. Nucleic Acids Research 1983; 11(13): 4629–4634.
Myers EW. Incremental Alignment Algorithms and Their Applications, Technical Report 86-22, Department of Computer Science, University of Arizona, Tucson, AZ 85721, 1986.
Myers EW. A sublinear algorithm for approximate keyword searching. Algorithmica 1994; 12: 345–374.
Rajasekaran S, Balla S, Huang CH. Exact Algorithms for Planted Motif Challenge Problems, Proc. Asia-Pacific Bioinformatics Conference (APBC), 2005: 249–260.
Sagot MF. Spelling approximate repeated or common motifs using a suffix tree. Springer-Verlag LNCS 1998; 1380: 111–127.
Ukkonen E. Finding approximate patterns in strings. Journal of Algorithms 1985; 6: 132–137.