A LOCAL-GLOBAL GENE COMPARISON FOR ORTHOLOG DETECTION IN TWO CLOSELY RELATED EUKARYOTES SPECIES

Resumen

ABSTRACT
Ortholog detection has included the comparison of different gene features to build a phylogenetic tree or the initial genome correspondence graph. Many pre-processing procedures have been applied to prune graph structures before the clustering of potential orthologs. Then, some post-processing improvements have contributed in (>90%) of precision. Although, some algorithms yield high levels of precision, it is still the main target for comparative genomics community. In this paper, we present an ortholog detection algorithm which combines sequence homology, length and global genomes rearrangements into a novel local-global gene dissimilarity measure for the comparison of two closely related eukaryotes species. We use Locally Collinear Blocks reported by the “Multiple Alignment of Conserved Genomic Sequence with Rearrangements” software (MAUVE) to take into account global genome rearrangements. We build a weighted undirected complete bipartite graph representing the comparison of the two genomes with the global gene dissimilarity measure. The pre-processing step eliminates all edges with weight over 20% of the minimum weight. Next, we resolve ambiguities by keeping matches within synteny blocks. Finally, in the clustering process we search for Best Unambiguous Subsets representing homology groups and pairs of orthologs. We present an experiment with S. Cerevisiae and S. Bayanus with 98.45% of true classifications.

KEYWORDS: Ortholog Detection Algorithms, Similarity Measures, Bipartite Graph Partitioning

RESUMEN
La detección de ortólogos ha incluido la comparación de diferentes rasgos de los genes para construir un árbol filogenético o un grafo de correspondencia entre genomas. Se han aplicado múltiples procedimientos de pre-procesamiento para podar las estructuras de grafos antes de agrupar los ortólogos potenciales. Además algunas mejoras de post-procesamiento han contribuido a (>90%) de precisión. A pesar de que algunos algoritmos arrojan altos niveles de precisión, ésta continúa siendo el principal objetivo de la comunidad científica que trabaja en genómica comparativa. En este trabajo presentamos un algoritmo de detección de ortólogos que combina la homología de las secuencias, la longitud y los reordenamientos globales en una nueva medida de disimilaridad entre genes local-global para la comparación de dos especies de eucariotas estrechamente relacionadas. Para tener en cuenta los reordenamientos globales de los genomas, utilizamos los Bloques Localmente Colineales reportados por el software de alineamiento múltiple de secuencias genómicas conservadas con reordenamientos “Multiple Alignment of Conserved Genomic Sequence with Rearrangements” (MAUVE). Construimos un grafo bipartito completo que representa la comparación entre los dos genomas con las medidas de disimilaridad globales entre los genes. El paso de pre-procesamiento elimina todos los arcos con peso por encima del 20% del mínimo peso. Luego resolvemos las ambigüedades conservando las correspondencias dentro de los bloques de orden conservado. Finalmente, en el paso de agrupamiento, buscamos los mejores subconjuntos no ambiguos que representan los grupos de homología y los pares de ortólogos. Presentamos un experimento con S. Cerevisiae y S. Bayanus con 98.45% de clasificaciones verdaderas.