The Algorithmic of Gene Teams Export

@incollection{bergeron:gene_teams, abstract = {Comparative genomics is a growing field in computational biology, and one of its typical problem is the identification of sets of orthologous genes that have virtually the same function in several genomes. Many different bioinformatics approaches have been proposed to define these groups, often based on the detection of sets of genes that are ” not too far” in all genomes. In this paper, we propose a unifying concept, called gene teams, which can be adapted to various notions of distance. We present two algorithms for identifying gene teams formed by n genes placed on m linear chromosomes. The first one runs in O(m 2 n 2) time, and follows a direct and simple approach. The second one is more tricky, but its running time is O(mnlog2(n)). Both algorithms require linear space. We also discuss extensions to circular chromosomes that achieve the same complexity.}, author = {Bergeron, Anne and Corteel, Sylvie and Raffinot, Mathieu}, citeulike-article-id = {3924130}, citeulike-linkout-0 = {http://dx.doi.org/10.1007/3-540-45784-4_36}, citeulike-linkout-1 = {http://www.springerlink.com/content/5djrqjbc0p138l4p}, doi = {10.1007/3-540-45784-4_36}, journal = {Algorithms in Bioinformatics}, keywords = {gene\_order, gene\_teams, synteny, thesis}, pages = {464--476}, posted-at = {2009-01-22 15:30:31}, priority = {2}, title = {The Algorithmic of Gene Teams}, url = {http://dx.doi.org/10.1007/3-540-45784-4_36}, year = {2002} }

TY - CHAP ID - bergeron:gene_teams L3 - citeulike-article-id:3924130 N2 - Comparative genomics is a growing field in computational biology, and one of its typical problem is the identification of sets of orthologous genes that have virtually the same function in several genomes. Many different bioinformatics approaches have been proposed to define these groups, often based on the detection of sets of genes that are “not too far” in all genomes. In this paper, we propose a unifying concept, called gene teams, which can be adapted to various notions of distance. We present two algorithms for identifying gene teams formed by n genes placed on m linear chromosomes. The first one runs in O(m 2 n 2) time, and follows a direct and simple approach. The second one is more tricky, but its running time is O(mnlog2(n)). Both algorithms require linear space. We also discuss extensions to circular chromosomes that achieve the same complexity. JF - Algorithms in Bioinformatics EP - 476 TI - The Algorithmic of Gene Teams SP - 464 KW - gene_order KW - gene_teams KW - synteny KW - thesis AU - Bergeron, Anne AU - Corteel, Sylvie AU - Raffinot, Mathieu PY - 2002/// UR - http://dx.doi.org/10.1007/3-540-45784-4_36 ER -