Vai ai contenuti. | Spostati sulla navigazione | Spostati sulla ricerca | Vai al menu | Contatti | Accessibilità

logo del sistema bibliotecario dell'ateneo di padova

Pierobon, Marco (2012) Minimization of the Crossing Number in a Reconciled Tree. [Magistrali biennali]

Full text disponibile come:

[img]
Preview
PDF
693Kb

Abstract

The problem of building a reconciled tree from a gene and a species tree is of great interest in bioinformatics, since it allows to highlight the relation between the evolution of the genes with the evolution of one or more species. In particular, a reconciled tree with a minimized number of crossings can help tracing down accurately the biological events of interest and avoiding wrong assumptions on the available data. The way the operation is performed affects heavily the usefulness of the resulting tree. The Minimized Crossing Number in a Reconciled Tree problem(MCNRT) problem is an NP-Complete problem. In this thesis we present an heuristic that aims to provide a solution for this problem. The proposed algorithm is based on the solution of the Generalized Tanglegram Layout problem, that has been adapted to work for the whole tree structure. Finally, the algorithm has been integrated in a running project, namely PrimeTV. The resulting code has been tested and proved able to optimize the number of crossings under different conditions

Item Type:Magistrali biennali
Corsi di Diploma di Laurea:Scuola di Ingegneria > Ingegneria Informatica
Scuola di Ingegneria > Ingegneria Informatica
Uncontrolled Keywords:Minimazation, Reconciled Tree
Subjects:Area 09 - Ingegneria industriale e dell'informazione > ING-INF/05 Sistemi di elaborazione delle informazioni
Codice ID:41554
Relatore:Pizzi, Cinzia
Correlatore:Arvestad, Lars
Data della tesi:22 October 2012
Biblioteca:Polo di Ingegneria > Biblioteca di Ingegneria dell'Informazione e Ingegneria Elettrica "Giovanni Someda"
Tipo di fruizione per il documento:on-line per i full-text

Solo per lo Staff dell Archivio: Modifica questo record