Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
MICA: Phần mềm máy tính để bàn cho việc tìm kiếm toàn diện trong các cơ sở dữ liệu DNA
Tóm tắt
Các nhà sinh học phân tử làm việc với các cơ sở dữ liệu DNA thường bao gồm toàn bộ hệ gen. Một yêu cầu phổ biến là tìm kiếm trong cơ sở dữ liệu DNA để tìm các kết quả trùng khớp chính xác cho một truy vấn không suy biến hoặc một truy vấn suy biến một phần. Các chương trình phần mềm hiện có cho mục đích này thường được thiết kế để chạy trên các máy chủ từ xa, nhưng một lựa chọn hấp dẫn là làm việc với các cơ sở dữ liệu DNA được lưu trữ trên máy tính cục bộ. Chúng tôi mô tả một chương trình phần mềm máy tính để bàn có tên là MICA (K-M er I ndexing with C ompact A rrays) cho phép tìm kiếm hiệu quả các cơ sở dữ liệu DNA lớn bằng cách sử dụng rất ít bộ nhớ. MICA lập chỉ mục nhanh chóng một cơ sở dữ liệu DNA. Trên máy tính Macintosh G5, toàn bộ hệ gen của con người có thể được lập chỉ mục trong khoảng 5 phút. Thuật toán lập chỉ mục nhận biết tất cả 15 ký tự của bảng chữ cái DNA và ghi lại đầy đủ thông tin trong bất kỳ chuỗi DNA nào, tuy nhiên đối với một chuỗi điển hình có độ dài L, chỉ mục chỉ chiếm khoảng 2L byte. Chỉ mục có thể được tìm kiếm để trả về danh sách đầy đủ các kết quả trùng khớp chính xác cho một truy vấn không suy biến hoặc suy biến một phần có bất kỳ độ dài nào. Một tìm kiếm điển hình của một chuỗi DNA dài chỉ liên quan đến việc đọc một phần nhỏ của chỉ mục vào bộ nhớ. Do đó, tốc độ tìm kiếm vẫn nhanh ngay cả khi RAM có sẵn bị hạn chế. MICA là một công cụ tìm kiếm phù hợp cho phần mềm phân tích DNA trên máy tính để bàn.
Từ khóa
#MICA #DNA #cơ sở dữ liệu #tìm kiếm hiệu quả #lập chỉ mục #phần mềm máy tính để bànTài liệu tham khảo
Gusfield D: Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge, Cambridge University Press; 1997:534.
Kurtz S, Philippy A, Delcher AL, Smoot M, Shumway M, Antonescu C, Salzberg SL: Versatile and open software for comparing large genomes. Genome Biol 2004, 5: R12. 10.1186/gb-2004-5-2-r12
Abouelhoda MI, Kurtz S, Ohlebusch E: Replacing suffix trees with enhanced suffix arrays. J Discrete Algorithms 2004, 2: 53–86. 10.1016/S1570-8667(03)00065-0
Lippert RA, Mobarry CM, Walenz BP: A space-efficient construction of the Burrows-Wheeler transform for genomic data. J Comp Biol 2005, 12: 943–951. 10.1089/cmb.2005.12.943
Ning A, Cox AJ, Mullikin JC: SSAHA: a fast search method for large DNA databases. Genome Res 2001, 11: 1725–1729. 10.1101/gr.194201
Kent WJ: BLAT-The BLAST-like alignment tool. Genome Res 2002, 12: 656–664. 10.1101/gr.229202. Article published online before March 2002
Pearson WR, Lipman DJ: Improved tools for biological sequence comparison. Proc Natl Acad Sci USA 1988, 85: 2444–2448. 10.1073/pnas.85.8.2444
Altschul SF, Gish W, Miller W, Myers EW, Lipman DJ: Basic local alignment search tool. J Mol Biol 1990, 215: 403–410. 10.1006/jmbi.1990.9999
Altschul SF, Madden TL, Schaffer AA, Zhang J, Zhang Z, Miller W, Lipman DJ: Gapped BLAST and PSI-BLAST: a new generation of protein database search programs. Nucleic Acids Res 1997, 25: 3389–3402. 10.1093/nar/25.17.3389
FASTA format description [http://www.ncbi.nlm.nih.gov/BLAST/fasta.shtml]
Knuth DE: The Art of Computer Programming. Volume 3: Sorting and Searching. 2nd edition., Addison-Wesley; 1998:800.
Ensembl Genome Browser [http://www.ensembl.org/index.html]
Greene WA: k-way merging and k-ary sorts: ; Birmingham, AL. 31st Annual ACM Southeast Conference 1993, 127–135.
Price AL, Eskin E, Pevzner PA: Whole-genome analysis of Alu repeat elements reveals complex evolutionary history. Genome Res 2004, 14: 2245–2252. 10.1101/gr.2693004
Hunt E: The suffix sequioa index for approximate string matching. DCS Tech Report, Dept of Computing Science, University of Glasgow, http://wwwdcsglaacuk/publications/PAPERS/7185/TR-2003–135pdf 2003, 1–26.
Reneker J, Shyu CR, Zeng P, Polacco JC, Gassmann W: ACMES: fast multiple-genome searches for short repeat sequences with concurrent cross-species information retrieval. Nucleic Acids Res 2004, 32: W649-W653.
Reneker J, Shyu CR: Refined repetitive sequence searches utilizing a fast hash function and cross species information retrievals. BMC Bioinformatics 2005, 3: 111. 10.1186/1471-2105-6-111
Crawford I, Wadleigh K: Software Optimization for High Performance Computing: Creating Faster Applications., Prentice Hall; 2000:377.
Rombauts S, Van de Peer Y, Rouzé P: AFLPinSilico, simulating AFLP fingerprints. Bioinformatics 2003, 19: 776–777. 10.1093/bioinformatics/btg090
Bikandi J, San Millán R, Rementeria A, Garaizar J: In silico analysis of complete bacterial genomes: PCR, AFLP-PCR and endonuclease restriction. Bioinformatics 2004, 5: 798–799. 10.1093/bioinformatics/btg491
Lexa M, Horak J, Brzobohaty B: Virtual PCR. Bioinformatics 2001, 17: 192–193. 10.1093/bioinformatics/17.2.192
Boutros PC, Okey AB: PUNS: transcriptomic- and genomic-in silico PCR for enhanced primer design. Bioinformatics 2004, 20: 2399–2400. 10.1093/bioinformatics/bth257
Rotmistrovsky K, Jang W, Schuler GD: A web server for performing electronic PCR. Nucleic Acids Res 2004, 32: W108-W112. 10.1093/nar/gnh102
Murphy K, Raj T, Winters RS, White PS: me-PCR: a refined ultrafast algorithm for identifying sequence-defined genomic elements. Bioinformatics 2004, 20: 588–590. 10.1093/bioinformatics/btg466
Li M, Ma B, Kisman D, Tromp J: Patternhunter II: highly sensitive and fast homology search. J Bioinform Comput Biol 2004, 2: 417–439. 10.1142/S0219720004000661
Noé L, Kucherov G: Improved hit criteria for DNA local alignment. BMC Bioinformatics 2004, 5: 149. 10.1186/1471-2105-5-149
Ning Z, Spooner W, Spargo A, Leonard S, Rae M, Cox A: The SSAHA trace server. Proceedings of the 2004 IEEE Computational Systems Bioinformatics Conference (CSB 2004) 2004, 544–545.
Wu TD, Watanabe CK: GMAP: a genomic mapping and alignment program for mRNA and EST sequences. Bioinformatics 2005, 21: 1859–1875. 10.1093/bioinformatics/bti310