The week's pick
Reseach Article
Implementation of Bit-Vector Algorithm for Approximate String Matching on Rhodopsin Protein Sequence
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 72 - Number 14 |
| Year of Publication: 2013 |
| Authors: Yessica Nataliani, Theophilus Wellem |
10.5120/12565-9214
|
Yessica Nataliani, Theophilus Wellem . Implementation of Bit-Vector Algorithm for Approximate String Matching on Rhodopsin Protein Sequence. International Journal of Computer Applications. 72, 14 ( June 2013), 34-38. DOI=10.5120/12565-9214
Abstract
Approximate string matching has been used in many applications such as, text retrieval, spell checker and DNA sequence matching in computational biology. In this paper, we implemented bit-vector algorithm using MATLAB for approximate string matching on Rhodopsin protein sequence of class Aves. Our experiments on real data of Rhodopsin protein sequences demonstrate that the algorithm can work as expected. The experiment results shows that the Rhodopsin protein sequence of the species in same genus is more approximately match each other compared to the species from different genus in the same family, Furthermore, for the species from different genus in the same family, its Rhodopsin protein sequence is more approximately match each other compared to the species from different family in the same order.
References
- Lok-Lam Cheng, David W. Cheung, and Siu-Ming Yiu. Approximate string matching in {DNA} sequences. In Proceedings of the Eight International Conference on Database Systems for Advanced Applications, {DASFAA} '03, pages 303–310, Washington, DC, USA, 2003. IEEE Computer Society.
- Zheng Liu, Xin Chen, James Borneman, and Tao Jiang. A Fast Algorithm for Approximate String Matching on Gene Sequences. 2005.
- Stephen F. Altschul, Warren Gish, Webb Miller, Eugene W. Myers, and David J. Lipman. Basic local alignment search tool. Journal of Molecular Biology, 215(3):403–410, October 1990.
- D J Lipman and W R Pearson. Rapid and sensitive protein similarity searches. Science (New York, N. Y. ), 227(4693):1435–1441, March 1985.
- Gene Myers. A fast bit-vector algorithm for approximate string matching based on dynamic programming. Journal of the ACM, 46(3):395–415, May 1999.
- B. J. Litmann and D. C. Mitchell. Rhodopsin structure and function. In A. G. Lee, editor, Rhodopsin and G-Protein Linked Receptors Vol. 2, Part A, pages 1–32. JAI Press, 1996.
- Heikki Hyyro. Explaining and extending the bit-parallel approximate string matching algorithm of Myers. Technical report, Dept. of Computer and Information Sciences, University of Tampere, Finland, 2001.
- V. I. Levenshtein. Binary codes capable of correcting deletions, insertions and reversals. Soviet Physics Doklady, 10:707–710, 1966.
- Peter H Sellers. The theory and computation of evolutionary distances: Pattern recognition. Journal of Algorithms, 1(4):359–373, December 1980.
- Esko Ukkonen. Algorithms for approximate string matching. Information Control, 64(1-3):100–118, March 1985.
- Petteri Jokinen, Jorma Tarhio, and Esko Ukkonen. A comparison of approximate string matching algorithms. Software - Practice and Experience, 26(12):1439–1458, December 1996.
- Gonzalo Navarro. A guided tour to approximate string matching. ACM Computing Survey, 33(1):31–88, March 2001.
- D. Huson. Bit-Vector-based Approximate String Matching. http://ab. inf. uni-tuebingen. de/teaching/ws04/seqana/script/bitvector. pdf, 2004.
- Universal Protein Resource (UniProt) Consortium website}. http://www. uniprot. org/taxonomy.
- DNA Data Bank of Japan (DDBJ) website. http://www. ddbj. nig. ac. jp.
Index Terms
Keywords