2017/05/02 by Mark Jones, Jones, Mark, Manuel Lafond +4
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Biomedical Text Mining and Ontologies #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Genomics and Phylogenetic Studies
paper · pdf · doi:10.48550/arxiv.1705.01240
openalex publication_date 2017/05/02 · openalex created_date 2022/09/06 · openalex updated_date 2026/07/28
Orthology and paralogy relations are often inferred by methods based on gene\nsimilarity, which usually yield a graph depicting the relationships between\ngene pairs. Such relation graphs are known to frequently contain errors, as\nthey cannot be explained via a gene tree that both contains the depicted\northologs/paralogs, and that is consistent with a species tree S. This idea\nof detecting errors through inconsistency with a species tree has mostly been\nstudied in the presence of speciation and duplication events only. In this\nwork, we ask: could the given set of relations be consistent if we allow\nlateral gene transfers in the evolutionary model? We formalize this question\nand provide a variety of algorithmic results regarding the underlying problems.\nNamely, we show that deciding if a relation graph R is consistent with a\ngiven species network N is NP-hard, and that it is W[1]-hard under the\nparameter "minimum number of transfers". However, we present an FPT algorithm\nbased on the degree of the DS-tree associated with R. We also study\nanalogous problems in the case that the transfer highways on a species tree are\nunknown.\n