A Low-complexity Distance for DNA Strings

• Autorzy: Dinu L.P. , Sgarro A.
• Języki publikacji: EN

Abstrakty

EN

We exhibit a low-complexity but non-trivial distance between strings to be used in biology. The experimental results we provide were obtained on a standard laptop and, even if preliminary, are quite encouraging.

Słowa kluczowe

EN

metric; rank distance; DNA sequencing; bioinformatics; phylogeny

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2006
• Tom: Vol. 73, nr 3
• Strony: 361--372
• Opis fizyczny: bibliogr. 14 poz.

Twórcy

autor

Dinu L.P.

autor

Sgarro A.

• University of Bucharest, Faculty of Mathematics and Computer Science, Academiei 14 , 010014, Bucharest, Romania,

Bibliografia

• [1] Y. Cao, A. Janke, P. J.Waddell, M.Westerman, O. Takenaka, S.Murata, N. Okada, S. Paabo,M. Hasegawa, Conflict among individual mitochondrial proteins in resolving the phylogeny of Eutherian orders, J. Mol. Evol., 47(1998), 307-322.
• [2] S.C. Chan, A.K.C. Wong and D.K.Y. Chiu, A survey of multiple sequence comparison methods, Bulletin of Math. Biology, Vol. 54 no.4 (1992) pp 563-598, 1992.
• [3] P. Diaconis, R. L. Graham, Spearman footrule as aMeasure of Disarray, Journal of Royal Statistical Society. Series B (Methodological), 39(2), 262-268, 1977.
• [4] A. Dinu, L.P. Dinu. On the Syllabic Similarities of Romance Languages. In A. Gelbukh (Ed.): CICLing 2005. LNCS 3406, 785-788, 2005.
• [5] L.P.Dinu, F. Manea. An efficient approach for the rank aggregation problem. (submitted, available at http://funinf.cs.unibuc.ro/~ldinu/dm2005.pdf)
• [6] C. de la Higuera, F. Casacuberta, Topology of strings: Median string is NPcomplete, Theor. Comp. Sci., 230, 39-48, 2000.
• [7] E.V. Koonin. The emerging paradigm and open problems in comparative genomics. Bioinformatics, 15, 265-266, 1999
• [8] J.A. Lake and J.E.Moore. Philogenetic analysis and comparative genomics. Trends guide to bioinformatics, Trends Journal Supplement 22-23, 1998
• [9] M. Li, X. Chen, X. Li, B. Ma, and Paul M.B. Vitanyi. The Similarity Metric. IEEE Transaction on Information Theory, 50:12(2004), 3250-3264, 2004.
• [10] A.W-C. Liew, H. Yan, M. Yang. Pattern recognition techniques for the emerging field of bioinformatics: A review Pattern Recognition, 38 (2005), 2055-2073
• [11] Marcus, S. Linguistic structures and generative devices in molecular genetics. Cahiers Ling. Theor. Appl., 11, 77-104, 1974
• [12] A. Reyes, C. Gissi, G. Pesole, F. M. Catzeflis, and C. Saccone Where Do Rodents Fit? Evidence from the Complete Mitochondrial Genome of Sciurus vulgaris . Mol. Biol. Evol. 17(6):979 - 983. 2000
• [13] T.F. Smith, M.S. Waterman, Comparison of biosequences, Adv. Appl. Math. 2 (1981) 482-489
• [14] J.C.Wooley. Trends in computational biology: a summary based on a RECOMB plenary lecture. J. Comput. Biology, 6, 459-474, 1999