Look-up in Google Scholar
Title: Cálculo da distância de reversão e construção de árvores filogenéticas usando a ordem dos genes
Other Titles: Cálculo de la distancia de reversión y construcción de árboles filogenéticos usando el orden de los genes
Advisor(s): Ayala Rincón, Mauricio
OCDE field: http://purl.org/pe-repo/ocde/ford#1.02.01
Issue Date: 3-Mar-2017
Institution: Universidade de Brasília
Abstract: Calcular distancias evolutivas, como la distancia de inversión o la distancia de doble corte y unión, entre las órdenes del gen de dos organismos es un problema combinatorio complejo. Este escenario puede ser aún más complicado si queremos construir árboles filogenéticos, ya que la mayoría de los enfoques en la literatura primero resuelve el problema mediano para tres genomas, que se demostró que es NP-Hard para varios modelos evolutivos. En este trabajo, proponemos varios algoritmos evolutivos para el problema de ordenar permutaciones (sin signo) por inversiones, cuya salida es la distancia de inversión. Estos algoritmos se basan en un algoritmo genético simple, en el que se integraron diferentes heurísticas, como la búsqueda local, el aprendizaje basado en la oposición y la eliminación de puntos de interrupción. Los experimentos se realizaron utilizando diferentes tipos de datos (permutaciones) basados ​​en órdenes de genes que se generaron artificialmente (de forma aleatoria) y también a partir de datos biológicos. A partir de estos algoritmos, los que tienen los mejores resultados para casos prácticos, es decir, permutaciones de longitud de hasta 120, se denominan AMBO y AMBO-Hibrido. Estos resultados fueron validados aplicando las pruebas estadísticas de Friedman y Holm. Además, se implementó un software llamado HELPHY para construir árboles filogenéticos, que toma como datos de entrada basados ​​en el orden de los genes (permutaciones firmadas). Primero, se propuso un algoritmo ambicioso para el pequeño problema de filogenia, cuyo objetivo es calcular el costo (puntaje) de una estructura de árbol dada. Luego, se propuso un enfoque basado en la búsqueda de vecindad variable para el gran problema de filogenia, cuyo objetivo es explorar el espacio de búsqueda de las estructuras de los árboles. Los resultados de los experimentos mostraron que HELPHY mejoró el tiempo de ejecución para encontrar buenos puntajes (distancia de inversión) para el conjunto de datos Campanulaceae; además, se encontró una nueva estructura de árbol con el mejor puntaje (doble corte y distancia de unión) en la literatura para el conjunto de datos de Hemiascomycetes.
Discipline: Ciencias naturales
Grade or title grantor: Universidade de Brasília. Instituto de Ciências Exatas. Departamento de Ciência da Computação
Grade or title: Doctor en Informática
Register date: 22-May-2020

Files in This Item:
File Description SizeFormat 
Soncco_Alvarez_JL.pdf
  Restricted Access
Tesis (abierta en repositorio de origen)1.39 MBAdobe PDFView/Open Request a copy
Autorizacion.pdf
  Restricted Access
Formato de autorización112.74 kBAdobe PDFView/Open Request a copy


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.