A Biclique Approach to Reference-Anchored Gene Blocks and Its Applications to Genomic Islands

[摘要] We formalize a new problem variant in gene-block discovery, denoted Reference-Anchored Gene Blocks (RAGB), given a query sequenceQof lengthn, representing the gene array of a DNA element, a window size bounddon the length of a substring of interest inQ, and a set of target gene sequences. Our objective is to identify gene blocks inthat are centered in a subsetqof co-localized genes fromQ, and contain genomes fromin which the corresponding orthologs of the genes fromqare also co-localized. We cast RAGB as a variant of a (colored) biclique problem in bipartite graphs, and analyze its parameterized complexity, as well as the parameterized complexity of other related problems. We give antime algorithm for the uncolored variant of our biclique problem, wheremis the number of areas of interest that are parsed from the target sequences, andnanddare as defined earlier. Our algorithm can be adapted to compute all maximal bicliques in the graph within the same time complexity, and to handle edge weights with a slightincrease to its time complexity. For the colored version of the problem, our algorithm has a time complexity of. We implement the algorithm and exemplify its application to the data mining of proteobacterial gene blocks that are centered in predicted proteobacterial genomic islands, leading to the identification of putatively mobilized clusters of virulence, pathogenicity, andresistance genes.

[学科分类] 生物科学（综合）

[关键词] bicliques;bipartite graphs;gene blocks;genomic islands;parameterized complexity