The week's pick
Random Articles
Reseach Article
A Model for identification of Length of Longest Common Subsequence by SRLCS
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 33 - Number 9 |
| Year of Publication: 2011 |
| Authors: Sumathy Eswaran, Dr.S P Rajagopalan |
10.5120/4049-5811
|
Sumathy Eswaran, Dr.S P Rajagopalan . A Model for identification of Length of Longest Common Subsequence by SRLCS. International Journal of Computer Applications. 33, 9 ( November 2011), 17-21. DOI=10.5120/4049-5811
Abstract
Longest Common Sequence problem is the most fundamental task in Computational Biology. This is not only a classical problem but also a challenging problem in bio sequences application. Many algorithms are being developed and these are discussed in terms of resource utilization efficiency. This paper proposes a model based on SRLCS algorithm [11] to obtain the possible length of Longest Common Sequence (LCS). The model accounts the length of the sequences under consideration, the identity and similarity between them. The model is obtained by regressing the LCS results on the training data set by SRLCS. The model so obtained is a simple linear expression which gives the predicted length of LCS. The possible Length of LCS between the given sequences is a sufficient heuristic for biologists in decision making. Often such a result is useful while working on homology finding.
References
- A.Aho, D.Hirschberg and Jullman, 1976, Bounds on the Complexity of the Longest Common Subsequence Problem, J.Assoc.Comput.Mach., Vol. 23, No.1,1976
- Blum, C.; Blesa, M. J.; and L´opez-Ib´a´nez, M. 2009. Beam search for the longest common subsequence problem. Comput. Oper. Res. 36(12):3178–3186.
- Edgar, R.C. MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Research, Vol. 32, No. 5, , 2004, 1792-1797
- Hirschberg, D. S. 1977. Algorithms for the longest common subsequence problem. J. ACM 24(4):664–675.
- The Pfam database is a large collection of protein families available at http://pfam.sanger.ac.uk/
- Needleman SB, Wunsch CD: A general method applicable to the search for similarities in the amino acid sequence of two proteins. J Mol Biol, 48(3):443-453, 1970.
- Qingguo Wang, Dmitry Korkin and Yi Shang , Efficient Dominant Point Algorithms for the Multiple Longeset Common Subsequence(MLCS) problem , IJCAI 2009. 1494–1500.
- Shyu, S. J., and Tsai, C.-Y. 2009. Finding the longest common subsequence for multiple biological sequences by ant colony optimization. Comput. Oper. Res. 36(1):73–91.
- Smith t.F., Waterman M.S, Identification of common molecular subsequence, Journal of Molecular Biology, Vol.215, 1990
- Sumathy Eswaran , S.P.Rajagopalan, An Efficient Fast Pruned Algorithm for finding Longest Common Sequences in Bio Sequences, Annals.Computer Science Series, 8th Tome, 1st Fasc, page 137 – 150, 2010.
- Sumathy Eswaran, S.P.Rajagopalan , “Heuristic SRLCS Algorithm to determine the proper alignment strategy for Biosequences , International Journal of Research and Reviews in Information Technology (IJRRIT) ,Vol. 1, No. 2, ,1-7, June 2011, ISSN: 2046-6501 12 Todd Easton, Abhilash Singireddy, 2008, A large neighborhood search heuristic for the longest common subsequence problem , J Heuristics(2008)14:271-283.
- Wei Liu, Lin Chen, A Fast Longest Common Subsequence Algorithm for Biosequences Alignment, IFIP vol 258, 2008.
- Yixi Chen, Andrew Wan and Wei Liu , A fast Parallel Algorithm for finding the Longest Common Subsequence of multiple biosequences , BMC Bioinformatics 2006, 7 (suppl 4): 54, ©2006 Chen et al; licensee BioMed Central Ltd.
Index Terms
Keywords