Wyszukiwanie przybliżone sekwencji DNA z użyciem indeksu FM

• Autorzy: Kawulok J.

Warianty tytułu

EN

Approximate matching of DNA sequences using FM-index

• Języki publikacji: PL

Abstrakty

PL

Artykuł opisuje nowy algorytm wyszukiwania przybliżonego zadanych fragmentów DNA w długich sekwencjach. Zgodnie z zaproponowanym podejściem poszukiwany fragment jest dzielony na nakładające się słowa, których pozycje w badanej sekwencji są wyznaczane przez użycie indeksu FM. Wykorzystując tak otrzymaną listę pozycji słów w sekwencji, poszukuje się połączeń spełniających założenie o dopuszczalnej maksymalnej liczbie różnic. Stworzony algorytm został poddany walidacji eksperymentalnej, której wyniki przedstawiono w artykule.

EN

This paper presents an algorithm for searching fragments of sequences in previously prepared DNA bases. The pattern is divided into words which overlap themselves. Their positions are found using FM-index, and they are used to search connections with each other under the assumption about a permissible maximum number of distinction.

Słowa kluczowe

PL

dopasowanie sekwencji; transformata Burrowsa-Wheelera; drzewo falkowe; indeks FM

EN

pattern matching; Burrows-Wheeler transform; wavelet tree; FM index

• Wydawca: Wydawnictwo Politechniki Śląskiej
• Czasopismo: Studia Informatica
• Rocznik: 2012
• Tom: Vol. 33, nr 2A
• Strony: 493--506
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Kawulok J.

• Politechnika Śląska, Instytut Informatyki, ul. Akademicka 16, 44-100 Gliwice, Polska,

Bibliografia

• 1. Altschul S. F., Gish W., Miller W., Myers E. W., Lipman D. J.: Basic local alignment search tool. J Mol Biol, Vol. 215(3), 1990, s. 403-410.
• 2. Baxevanis A., Ouellette B.: Bioinformatics: A Practical Guide to the Analysis of Genes and Proteins, edition 2. Wiley, 2001.
• 3. Benson D. A., Karsch-Mizrachi I., Lipman D. J., Ostell J., Sayers E. W.: GenBank. Nucleic Acids Res, Vol. 39, 2011, s. D37-D39.
• 4. Burrows M., Wheeler D.: A block sorting lossless data compression algorithm. Technical Report, Vol. 124, Digital Equipment Corporation, 1994.
• 5. Clark D.: Compact Pat Trees. PhD thesis. University of Waterloo, Canada 1996.
• 6. Claude F., Navarro G.: Practical rank/select queries over arbitrary sequences. Proc. 15th International Symposium on String Processing and Information Retrieval, LNCS, Vol. 5280, Springer-Verlag, 2008, s. 176-187.
• 7. Ferragina P., Manzini G.: Indexing compressed text. Journal of the ACM, Vol. 52, 2005, s. 552-581.
• 8. Ferragina P., Manzini G., Makinen V., Navarro G.: Compressed representations of sequences and full-text indexes. ACM Transactions on Algorithms, Vol. 3(2), 2007.
• 9. Grabowski S., Navarro G., Przywarski R., Salinger A., Makinen V.: A simple alphabet-independent FM-index. Int. J. Found. Comput. Sci., Vol. 17(6), 2006, s. 1365-1384.
• 10. Grossi R., Gupta A., Vitter J.: High-order entropy-compressed text indexes. SODA, 2003, s. 481-580.
• 11. Jacobson G.: Succinct Static Data Structures. PhD thesis. CMU-CS-89-112, Carnegie Mellon University, 1989.
• 12. Kent W.J.: BLAT - the BLAST-like alignment tool. Genome Research, Vol. 12(4), 2002, s. 656-664.
• 13. Makinen V., Navarro G.: New search algorithms and time/space tradeoffs for succinct suffix arrays. Tech. Rep. C-2004-20, University of Helsinki, 2004.
• 14. Needleman S., Wunsch C.: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J. Mol. Biol., Vol. 48(3), 1970, s. 443-453.
• 15. Okanohara D., Sadakane K.: Practical entropy-compressed rank/select dictionary. Proc. Workshop on Algorithm Engineering and Experiments, ALENEX, 2007.
• 16. Russo L. M., Navarro G., Oliveira A. L., Morales P.: Approximate String Matching with Compressed Indexes. Algorithms, Vol. 2, 2009, s. 1105-1136.
• 17. Smith T. F., Waterman M. S.: Identification of Common Molecular Subsequences. J. Mol. Biol., Vol. 147(1), 1981, s. 195-197.
• 18. Sonnhammer E.L., Durbin R.: A dot-matrix program with dynamic threshold control suited for genomic DNA and protein sequence analysis. Gene, Vol. 167(1-2), 1995.
• 19. Soumya R.: Computational text analysis for functional genomics and bioinformatics. Oxford University Press, New York 2006.
• 20. Välimäki N., Ladra S., Mäkinen V.: Approximate all-pairs suffix/prefix overlaps. CPM'10 Proceedings of the 21st annual conference on Combinatorial pattern matching, Springer-Verlag, 2010, s. 76-87.