Constraint Programming Models For Transposition Distance Problem

dc.creatorDias U.
dc.creatorDias Z.
dc.date2009
dc.date2015-06-26T13:36:30Z
dc.date2015-11-26T15:36:56Z
dc.date2015-06-26T13:36:30Z
dc.date2015-11-26T15:36:56Z
dc.date.accessioned2018-03-28T22:45:24Z
dc.date.available2018-03-28T22:45:24Z
dc.identifier3642032222; 9783642032226
dc.identifierLecture Notes In Computer Science (including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics). , v. 5676 LNBI, n. , p. 13 - 23, 2009.
dc.identifier3029743
dc.identifier10.1007/978-3-642-03223-3_2
dc.identifierhttp://www.scopus.com/inward/record.url?eid=2-s2.0-69949185523&partnerID=40&md5=d6db618502ee8c61620fcc6af4764b09
dc.identifierhttp://www.repositorio.unicamp.br/handle/REPOSIP/92560
dc.identifierhttp://repositorio.unicamp.br/jspui/handle/REPOSIP/92560
dc.identifier2-s2.0-69949185523
dc.identifier.urihttp://repositorioslatinoamericanos.uchile.cl/handle/2250/1263549
dc.descriptionGenome Rearrangements addresses the problem of finding the minimum number of global operations, such as transpositions, reversals, fusions and fissions that transform a given genome into another. In this paper we deal with transposition events, which are events that change the position of two contiguous block of genes in the same chromosome. The transposition event generates the transposition distance problem, that is to find the minimum number of transposition that transform one genome (or chromosome) into another. Although some tractables instances were found [20,14], it is not known if an exact polynomial time algorithm exists. Recently, Dias and Souza [9] proposed polynomial-sized Integer Linear Programming (ILP) models for rearrangement distance problems where events are restricted to reversals, transpositions or a combination of both. In this work we devise a slight different approach. We present some Constraint Logic Programming (CLP) models for transposition distance based on known bounds to the problem. © 2009 Springer Berlin Heidelberg.
dc.description5676 LNBI
dc.description
dc.description13
dc.description23
dc.descriptionApt, K., Wallace, M., (2007) Constraints Logic Programming using Eclipse, , Cambridge
dc.descriptionBafna, V., Pevzner, P.A., Sorting by reversals: Genome rearrangements in plant organelles and evolutionary history of X chromosome (1995) Molecular Biology and Evolution, 12 (2), pp. 239-246
dc.descriptionBafna, V., Pevzner, P.A., Sorting by Transpositions (1998) SIAM Journal on Discrete Mathematics, 11 (2), pp. 224-240
dc.descriptionBenoǐt-Gagńe, M., Hamel, S.: A New and Faster Method of Sorting by Transpositions. In: Ma, B., Zhang, K. (eds.) CPM 2007. LNCS, 4580, pp. 131-141. Springer, Heidelberg (2007)Caprara, A., Lancia, G., Ng, S.-K., A Column-Generation Based Branch-and-Bound Algorithm for Sorting by Reversals (1999) DIMACS Series in Discrete Mathematics and Theoretical Computer Science, 47, pp. 213-226. , The American Mathematical Society
dc.descriptionCaprara, A., Lancia, G., Ng, S.-K., Sorting Permutations by Reversals through Branch-and-Price (1999), Technical Report OR-99-1, DEIS, Operations Research Group, University of BolognaCaprara, A., Lancia, G., Ng, S.-K., Fast Practical Solution of Sorting by Reversals (2000) Proceedings of the 11th ACM-SIAM Annual Symposium on Discrete Algorithms (SODA, pp. 12-21. , San Francisco, USA, pp, ACM Press, New York
dc.descriptionChristie, D.A., (1998) Genome Rearrangement Problems, , PhD thesis, Glasgow University
dc.descriptionDias, Z., Souza, C., Polynomial-sized ILP Models for Rearrangement Distance Problems (2007) BSB 2007 Poster Proceedings
dc.descriptionDobzhansky, T., Sturtevant, A.H., Inversions in the third chromosome of wild races of Drosophila pseudoobscura, and their use in the study of the history of the species (1936) Proceedings of the National Academy of Science, 22, pp. 448-450
dc.descriptionThe Eclipse Constraint Programming System, , http://www.eclipse-clp.org, March 2009
dc.descriptionElias, I., Hartmn, T., A 1.375-Approximation Algorithm for Sorting by Transpositions (2006) Comput, pp. 369-379. , Trans, Biol. Bioinformatics 34
dc.descriptionEriksson, H., Eriksson, K., Karlander, J., Svensson, L., Wästlund, J., Sorting a Bridge Hand (2001) Discrete Math, 241 (1-3), pp. 289-300
dc.descriptionFortuna, V.J., (2005) Distǎncias de transposição entre genomas, , Master's thesis, Institute of Computing, University of Campinas
dc.descriptionHannenhalli, S., Pevzner, P.A., Transforming Cabbage into Turnip (Polynomial Algorithm for Sorting Signed Permutations by Reversals) (1995) Proceedings of the Twenty-Seventh Annual ACM Symposium on the Theory of Computing, pp. 178-189. , Las Vegas, USA, May
dc.descriptionHannenhalli, S., Pevzner, P.A., Transforming Men into Mice (Polynomial Algorithm for Genomic Distance Problem) (1995) Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS, pp. 581-592. , October, IEEE Computer Society Press, Los Alamitos () 1995
dc.descriptionHartman, T., Sharan, R., A Simpler 1.5-approximation Algorithm for Sorting by Transpositions , pp. 156-169. , Springer, Heidelberg 2003Hausen, R.A., Faria, L., Figueiredo, C.M.H., Kowada, L.A.B.: On the toric graph as a tool to handle the problem of sorting by transpositions. In: Bazzan, A.L.C., Craven, M., Martins, N.F. (eds.) BSB 2008. LNCS (LNBI), 5167, pp. 79-91. Springer, Heidelberg (2008)Kececioglu, J.D., Ravi, R.: Of Mice and Men: Algorithms for Evolutionary Distances Between Genomes with Translocation. In: Proceedings of the 6th Annual Symposium on Discrete Algorithms, January 1995, pp. 604-613. ACM Press, New York (1995)Labarre, A., New Bounds and Tractable Instances for the Transposition Distance (2006) IEEE/ACM Trans. Comput. Biol. Bioinformatics, 3 (4), pp. 380-394
dc.descriptionMarriott, K., Stuckey, P.J., (1998) Programming with Constraints: An Introduction, , MIT Press, Cambridge
dc.descriptionMira, C.V.G., Dias, Z., Santos, H.P., Pinto, G.A., Walter, M.E.: Transposition Distance Based on the Algebraic Formalism. In: Bazzan, A.L.C., Craven, M., Martins, N.F. (eds.) BSB 2008. LNCS (LNBI), 5167, pp. 115-126. Springer, Heidelberg (2008)Palmer, J.D., Herbon, L.A., Plant mitochondrial DNA evolves rapidly in structure, but slowly in sequence (1988) Journal of Molecular Evolution, 27, pp. 87-97
dc.descriptionWalter, M.E.M.T., Dias, Z., Meidanis, J., A New Approach for Approximating the Transposition Distance (2000) Proceedings of the String Processing and Information Retrieval (SPIRE, , September
dc.languageen
dc.publisher
dc.relationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
dc.rightsfechado
dc.sourceScopus
dc.titleConstraint Programming Models For Transposition Distance Problem
dc.typeActas de congresos


Este ítem pertenece a la siguiente institución