Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida

Esta tesis describe el problema de la subsecuencia común más larga y específicamente una de sus extensiones, el problema de la subsecuencia común más larga restringida. Esta es una de las operaciones de comparación más importantes sobre las secuencias y su aplicación es diversa en muchas áreas, espe...

Full description

Autores:
Soto Forero, Wilson Eduardo
Tipo de recurso:
Fecha de publicación:
2010
Institución:
Universidad Nacional de Colombia
Repositorio:
Universidad Nacional de Colombia
Idioma:
spa
OAI Identifier:
oai:repositorio.unal.edu.co:unal/70479
Acceso en línea:
https://repositorio.unal.edu.co/handle/unal/70479
http://bdigital.unal.edu.co/2754/
Palabra clave:
0 Generalidades / Computer science, information and general works
51 Matemáticas / Mathematics
62 Ingeniería y operaciones afines / Engineering
Algoritmos
Secuencias
Medida de similitud
Subscuencia común más larga
Subsecuencia común más larga restringida
Algorithms
Sequences
Similarity measure
Longest Common Subsequence (LCS)
Constrained Longest Common Subsequence (CLCS)
Rights
openAccess
License
Atribución-NoComercial 4.0 Internacional
id UNACIONAL2_321b65781a4c53de4c8617785a132c29
oai_identifier_str oai:repositorio.unal.edu.co:unal/70479
network_acronym_str UNACIONAL2
network_name_str Universidad Nacional de Colombia
repository_id_str
spelling Atribución-NoComercial 4.0 InternacionalDerechos reservados - Universidad Nacional de Colombiahttp://creativecommons.org/licenses/by-nc/4.0/info:eu-repo/semantics/openAccesshttp://purl.org/coar/access_right/c_abf2Pinzón Ardila, Yoan José (Thesis advisor)43d74dd2-0249-4820-bc3a-091bf37f8b0fSoto Forero, Wilson Eduardod9f09931-283b-4b3a-801b-9e7c6ec808673002019-07-03T13:21:59Z2019-07-03T13:21:59Z2010-06https://repositorio.unal.edu.co/handle/unal/70479http://bdigital.unal.edu.co/2754/Esta tesis describe el problema de la subsecuencia común más larga y específicamente una de sus extensiones, el problema de la subsecuencia común más larga restringida. Esta es una de las operaciones de comparación más importantes sobre las secuencias y su aplicación es diversa en muchas áreas, especialmente en la bioinformática. Principalmente esta tesis tiene dos contribuciones, i) el proponer un nuevo algoritmo para solucionar el problema de la subsecuencia común más larga restringida basado en el concepto de dominancia y ii) la realización de una evaluación experimental de los algoritmos más representativos para solucionar el problema de la subsecuencia común más larga restringida incluyéndose el algoritmo propuesto. El trabajo se complementa con una descripción de las técnicas más usuales para solucionar el problema de la subsecuencia común más larga como base para realizar posteriores trabajos en técnicas no aplicadas para solucionar el problema de la subsecuencia común más larga restringida. / Abstract. This thesis focuses on the longest common subsequence problem. Specifically, it focuses on one of its extensions, the constrained longest common subsequence problem (CLCS). The CLCS problem is one of the most important comparison operations on sequences, where its application is diverse in many areas, especially in bioinformatics. This thesis has two main contributions, i) To propose a new algorithm to solve the constrained longest common subsequence problem based on the concept of dominance, and ii) To perform an experimental evaluation of the most representative CLCS algorithms including the proposed algorithm. The work is complemented with a description of the state of the art techniques to solve the longest common subsequence problem. This description will be the basis of further work, which will pretend the development of novel techniques to solve the constrained longest common subsequence problem.Maestríaapplication/pdfspaUniversidad Nacional de Colombia Sede Bogotá Facultad de Ingeniería Departamento de Ingeniería de Sistemas e Industrial Ingeniería de SistemasIngeniería de SistemasSoto Forero, Wilson Eduardo (2010) Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida / Comparative study of algorithms for the constrained longest common subsequence problem. Maestría thesis, Universidad Nacional de Colombia.0 Generalidades / Computer science, information and general works51 Matemáticas / Mathematics62 Ingeniería y operaciones afines / EngineeringAlgoritmosSecuenciasMedida de similitudSubscuencia común más largaSubsecuencia común más larga restringidaAlgorithmsSequencesSimilarity measureLongest Common Subsequence (LCS)Constrained Longest Common Subsequence (CLCS)Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringidaComparative study of algorithms for the constrained longest common subsequence problemTrabajo de grado - Maestríainfo:eu-repo/semantics/masterThesisinfo:eu-repo/semantics/acceptedVersionTexthttp://purl.org/redcol/resource_type/TMORIGINAL299716.2010.pdfapplication/pdf3344720https://repositorio.unal.edu.co/bitstream/unal/70479/1/299716.2010.pdf21e218952e6bbe17f9eda5a05f571bacMD51THUMBNAIL299716.2010.pdf.jpg299716.2010.pdf.jpgGenerated Thumbnailimage/jpeg4774https://repositorio.unal.edu.co/bitstream/unal/70479/2/299716.2010.pdf.jpga084400d06d105a83f94434368ccdfebMD52unal/70479oai:repositorio.unal.edu.co:unal/704792024-06-06 23:09:22.96Repositorio Institucional Universidad Nacional de Colombiarepositorio_nal@unal.edu.co
dc.title.spa.fl_str_mv Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida
dc.title.translated.Spa.fl_str_mv Comparative study of algorithms for the constrained longest common subsequence problem
title Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida
spellingShingle Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida
0 Generalidades / Computer science, information and general works
51 Matemáticas / Mathematics
62 Ingeniería y operaciones afines / Engineering
Algoritmos
Secuencias
Medida de similitud
Subscuencia común más larga
Subsecuencia común más larga restringida
Algorithms
Sequences
Similarity measure
Longest Common Subsequence (LCS)
Constrained Longest Common Subsequence (CLCS)
title_short Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida
title_full Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida
title_fullStr Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida
title_full_unstemmed Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida
title_sort Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida
dc.creator.fl_str_mv Soto Forero, Wilson Eduardo
dc.contributor.advisor.spa.fl_str_mv Pinzón Ardila, Yoan José (Thesis advisor)
dc.contributor.author.spa.fl_str_mv Soto Forero, Wilson Eduardo
dc.subject.ddc.spa.fl_str_mv 0 Generalidades / Computer science, information and general works
51 Matemáticas / Mathematics
62 Ingeniería y operaciones afines / Engineering
topic 0 Generalidades / Computer science, information and general works
51 Matemáticas / Mathematics
62 Ingeniería y operaciones afines / Engineering
Algoritmos
Secuencias
Medida de similitud
Subscuencia común más larga
Subsecuencia común más larga restringida
Algorithms
Sequences
Similarity measure
Longest Common Subsequence (LCS)
Constrained Longest Common Subsequence (CLCS)
dc.subject.proposal.spa.fl_str_mv Algoritmos
Secuencias
Medida de similitud
Subscuencia común más larga
Subsecuencia común más larga restringida
Algorithms
Sequences
Similarity measure
Longest Common Subsequence (LCS)
Constrained Longest Common Subsequence (CLCS)
description Esta tesis describe el problema de la subsecuencia común más larga y específicamente una de sus extensiones, el problema de la subsecuencia común más larga restringida. Esta es una de las operaciones de comparación más importantes sobre las secuencias y su aplicación es diversa en muchas áreas, especialmente en la bioinformática. Principalmente esta tesis tiene dos contribuciones, i) el proponer un nuevo algoritmo para solucionar el problema de la subsecuencia común más larga restringida basado en el concepto de dominancia y ii) la realización de una evaluación experimental de los algoritmos más representativos para solucionar el problema de la subsecuencia común más larga restringida incluyéndose el algoritmo propuesto. El trabajo se complementa con una descripción de las técnicas más usuales para solucionar el problema de la subsecuencia común más larga como base para realizar posteriores trabajos en técnicas no aplicadas para solucionar el problema de la subsecuencia común más larga restringida. / Abstract. This thesis focuses on the longest common subsequence problem. Specifically, it focuses on one of its extensions, the constrained longest common subsequence problem (CLCS). The CLCS problem is one of the most important comparison operations on sequences, where its application is diverse in many areas, especially in bioinformatics. This thesis has two main contributions, i) To propose a new algorithm to solve the constrained longest common subsequence problem based on the concept of dominance, and ii) To perform an experimental evaluation of the most representative CLCS algorithms including the proposed algorithm. The work is complemented with a description of the state of the art techniques to solve the longest common subsequence problem. This description will be the basis of further work, which will pretend the development of novel techniques to solve the constrained longest common subsequence problem.
publishDate 2010
dc.date.issued.spa.fl_str_mv 2010-06
dc.date.accessioned.spa.fl_str_mv 2019-07-03T13:21:59Z
dc.date.available.spa.fl_str_mv 2019-07-03T13:21:59Z
dc.type.spa.fl_str_mv Trabajo de grado - Maestría
dc.type.driver.spa.fl_str_mv info:eu-repo/semantics/masterThesis
dc.type.version.spa.fl_str_mv info:eu-repo/semantics/acceptedVersion
dc.type.content.spa.fl_str_mv Text
dc.type.redcol.spa.fl_str_mv http://purl.org/redcol/resource_type/TM
status_str acceptedVersion
dc.identifier.uri.none.fl_str_mv https://repositorio.unal.edu.co/handle/unal/70479
dc.identifier.eprints.spa.fl_str_mv http://bdigital.unal.edu.co/2754/
url https://repositorio.unal.edu.co/handle/unal/70479
http://bdigital.unal.edu.co/2754/
dc.language.iso.spa.fl_str_mv spa
language spa
dc.relation.ispartof.spa.fl_str_mv Universidad Nacional de Colombia Sede Bogotá Facultad de Ingeniería Departamento de Ingeniería de Sistemas e Industrial Ingeniería de Sistemas
Ingeniería de Sistemas
dc.relation.references.spa.fl_str_mv Soto Forero, Wilson Eduardo (2010) Estudio comparativo de algoritmos para el problema de la subsecuencia común más larga restringida / Comparative study of algorithms for the constrained longest common subsequence problem. Maestría thesis, Universidad Nacional de Colombia.
dc.rights.spa.fl_str_mv Derechos reservados - Universidad Nacional de Colombia
dc.rights.coar.fl_str_mv http://purl.org/coar/access_right/c_abf2
dc.rights.license.spa.fl_str_mv Atribución-NoComercial 4.0 Internacional
dc.rights.uri.spa.fl_str_mv http://creativecommons.org/licenses/by-nc/4.0/
dc.rights.accessrights.spa.fl_str_mv info:eu-repo/semantics/openAccess
rights_invalid_str_mv Atribución-NoComercial 4.0 Internacional
Derechos reservados - Universidad Nacional de Colombia
http://creativecommons.org/licenses/by-nc/4.0/
http://purl.org/coar/access_right/c_abf2
eu_rights_str_mv openAccess
dc.format.mimetype.spa.fl_str_mv application/pdf
institution Universidad Nacional de Colombia
bitstream.url.fl_str_mv https://repositorio.unal.edu.co/bitstream/unal/70479/1/299716.2010.pdf
https://repositorio.unal.edu.co/bitstream/unal/70479/2/299716.2010.pdf.jpg
bitstream.checksum.fl_str_mv 21e218952e6bbe17f9eda5a05f571bac
a084400d06d105a83f94434368ccdfeb
bitstream.checksumAlgorithm.fl_str_mv MD5
MD5
repository.name.fl_str_mv Repositorio Institucional Universidad Nacional de Colombia
repository.mail.fl_str_mv repositorio_nal@unal.edu.co
_version_ 1814089948940206080