Speaker: Jens Stoye, Bielefeld University.
Date: 29 mar 2017, 16h.
Place: Room 407, Bloco H, IME, Campus Gragoatá, UFF.
Abstract: The search for common gene clusters within a set of genomes has been a central topic in computational comparative genomics for many years. The amount and size of groups of genes appearing closely together in the genomes of different species is a reliable measure for the degree of their relationship. Genes with a conserved neighborhood in various species' genomes can also give hints on an associated function or regulation.
To find such common gene clusters, a genome is often reduced to the order of its genes which are represented as a sequence of characters where homologous genes are represented by the same character. In this context, a common gene cluster is a set of genes that are co-located in the sequences of at least two genomes. Based on this representation, several mathematical models for gene clusters and algorithms to find them have been introduced during the last 20 years. All of them take into account the one-dimensional gene order in the genomic sequence without considering any spatial information regarding the three-dimensional structure of the chromatid in the cell.
We present for the first time a model that includes information about the spatial structure of the genomes to the gene cluster model. While an exponential time algorithm can simply be derived, it was so far impossible to find an exact algorithm working in polynomial time. On the other hand, it is open whether the problem is NP-hard.
Note: Joint work with Tizian Schulz. Professor Jens Stoye is a visiting professor at the Math Graduate Program at UFF, through the project "PVE/Ciência sem Fronteiras/CAPES" coordinated by Professor Simone Dantas.