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

1.1. The reference-anchored gene-block problem

We propose a new bioinformatic approach that is based on interrogating a given reference DNA element from a specific genome for subsets of genes that are conserved as proximity blocks across other microbial genomes. The subsequent computational problem is called the Reference-Anchored Gene Blocks (RAGB) problem. The input to this problem consists of the gene sequence of a reference DNA element, and a set of target genome sequences. The target sequences are then parsed, either via a simple sliding window approach or according to some a priori biological data, into areas of interest or segments of small proximity. The output of our problem are gene blocks that are clustered together in a small vicinity in the reference element, and that have orthologous genes clustered together in segments of sufficiently many target genomes. Note that our model allows paralogous occurrences of genes from the reference elements (i.e., a gene may appear more than once in a target genome), and moreover, we do not require that all input genomes be represented in an output block.

Our framework is based on a bipartite graph modulation. After the phase where the input element and genomes are parsed into (gene cluster encompassing) segments, a bipartite graph is constructed according to these segments. In this graph, vertices of one side represent subsets of reference genes, nodes on the other side represent segments from the target genomes, and edges connect the subsets of reference genes to segments from the target genomes that contain corresponding orthologs. Based on this, we cast the problem of enumerating RAGB as a special type of biclustering problem: Compute appropriately constrained bicliques in an input bipartite graph. The constraint is a bound that ensures the co-localization of the reference genes participating in a block. When it is necessary to distinguish between segments of different genomes, we color-code the vertices corresponding to segments in our bipartite graph, and we require colorful bicliques as solutions.

1.2. Our contribution

Since our problem translates to a computationally hard problem, we use the theory of parameterized complexity (Downey and Fellows, 1999), which provides a convenient theoretical framework for analyzing exact algorithms for hard problems. In particular, given a bipartite graph with n vertices corresponding to references genes, and m vertices corresponding to target segments, we show how to compute all maximal constrained bicliques in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( nm + {2^d}nm / \lg m )$$ \end{document} time, where d is the bound on the genomic distance between two genes in a cluster. We then show how to extend this algorithm to a weighted variant of the problem with an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( \lg d )$$ \end{document} increase to the time complexity. Finally, our algorithm can also be extended to the more challenging vertex-colored variant corresponding to the case where segments are overlapping sliding windows in the target genomes; however, we allow only one segment per genome in the output. The time complexity increases in this case to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O{ ( 2^d}nm )$$ \end{document} . We also use the theory of parameterized complexity to analyze closely related biclique problems, and we show that these are unlikely to admit efficient algorithms with respect to their natural parameterizations.

We implement our algorithm in a program called RAGB Monitor. This program enumerates conserved blocks that are centered in small components of a given input DNA element and ranks them according to a probabilistic ranking score. The program is exemplified by applying it to the data mining of 33 proteobacterial genomes for gene blocks that are centered in 558 predicted proteobacterial GIs from these genomes, leading to the identification and visualization of putatively mobilized clusters of virulence, pathogenicity, and resistance genes.

1.3. Related work

A gene block is a group of genes that are consistently clustered within the same genomic vicinity across a set of genomes, regardless of the internal order of the genes from the block in each genome. The clustered occurrences of these genes within the corresponding genomes are called instances of the block. The problem of discovering gene blocks in a set of input genomes has been thoroughly studied. In the most basic variant of this problem, denoted the Common Intervals in Permutations problem (Bergeron et al., 2002; Schmidt and Stoye, 2004), a chromosome is considered a permutation of distinct genes, such that each gene appears only once in a chromosome and a gene block is defined to be a set of genes that appear in all the input genomes without gaps. A more advanced problem variant, denoted the Approximate Clusters in Permutations problem (Béal et al., 2004), extends the basic model with the relaxation of allowing gaps (intermitting genes) within the genes of block instances. Another interesting variant of this problem is the Common Intervals in Strings problem (Amir et al., 2003, 2007): Here, the genomes are modeled as general strings rather than permutations. This enables the consideration of genomes with gene duplications (paralogs). Finally, in the most advanced problem variant, the Approximate Clusters in Strings problem, gaps are allowed, duplications and missing genes among input genomes are supported, and there is no requirement that a block instance be present in all input genomes (Kim et al., 2006; Ling et al., 2009; Jahn, 2011).

The problem introduced in our article could be viewed as a special variant of gene block discovery, where the sought gene block is characterized by a specific consensus set of genes, such that orthologs of all the genes from this consensus set are required to occur, clustered together, in a designated reference genome, as well as in a predefined quorum of the other input genomes. Within this problem definition, the model we follow in our solution to the problem is the most general one: It allows paralogous occurrences of genes in the input genomes, does not require gene order conservation across distinct instances of a given gene block within the input genomes, and does not require that all input genomes participate in a candidate solution.

Note that if a gene block is not represented by a consensus gene set that is common to all instances, but rather by a closely related set with a reference occurrence in a reference genome (i.e., one without intermitting or missing genes), then the search space becomes polynomially bounded (Amir et al., 2007; Jahn, 2011). In our application, however, the sought output per gene block entails a very specific consensus descriptor, consisting of a set of genes characterizing the identified block. It is required that an ortholog of each of the genes from this consensus gene set be found in each and every instance of the block (in the designated reference genome as well as in the target genomes), allowing for intermitting genes (gaps) but not substitutions or deletions of genes from the consensus gene set. The motivation for requiring such gene-content specificity is illustrated in Section 5 where we exemplify the genomic studies toward which we aim. These studies are based on comparative analysis within “families” of gene blocks whose members differ by slight gene content variations. Such analysis requires that each gene block be characterized by its consensus genes. Of course, this requirement comes at an expense to output size: As opposed to the reference-based approaches mentioned earlier, the output of our algorithms might be exponential in the size of the input, as it entails the distinct enumeration of gene subsets from (bounded-length windows of) the designated reference genome.

2.1. Parameterized complexity primer

We are interested in computing bicliques of certain properties in a bipartite graph. Since computing a biclique with a certain number of edges or vertices in a bipartite graph is NP complete (Garey and Johnson, 1979), any meaningful model for our problem will be non-deterministic polynomial time (NP) hard as well. Thus, we use the theory of parameterized complexity (Downey and Fellows, 1999) to cope with this hardness. Next, we provide a brief description of this theory, only mentioning elements that will be relevant for our scope.

Parameterized complexity facilitates the analysis of computational problems in terms of various instance parameters that may be independent of the total input length. In this way, problem instances are analyzed not only according to the total input length n but also according to an additional numerical parameter k that may encode other aspects of the input. Thus, formally a parameterized problem is a set of ordered pairs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( x , k ) \in { \{ 0 , 1 \} ^*} \times \mathbb{N}$$ \end{document} , where x encodes the combinatorial aspects of the input, and k is the parameter. A parameterized problem is considered tractable (formally, fixed-parameter tractable [FPT] for short) if there is an algorithm solving any instance \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( x , k )$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$f ( k ) \cdot \vert x{ \vert ^{O ( 1 ) }}$$ \end{document} time, where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$f ( )$$ \end{document} is allowed to be any arbitrary (even exponential) computable function that is independent of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert x \vert$$ \end{document} (the input length), and the exponent in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert x{ \vert ^{O ( 1 ) }}$$ \end{document} is required to be independent of k. For example, a running time of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${2^{O ( k ) }} \cdot {n^3}$$ \end{document} is considered feasible in the parameterized setting, whereas \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${n^{O ( k ) }}$$ \end{document} is considered infeasible. In this way, we can model scenarios where certain problem parameters are typically much smaller than the total input length, yet may not be small enough to be considered constant.

The most common way of showing that a certain parameterized problem is unlikely to have an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$f ( k ) \cdot \vert x{ \vert ^{O ( 1 ) }}$$ \end{document} time algorithm is via a parameterized reduction from a problem, which is hard for W[1], a class of problems that may be considered the parameterized analog of NP. A parameterized reduction from a parameterized problem \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${L_1} \subseteq { \{ 0 , 1 \} ^*} \times \mathbb{N}$$ \end{document} to a parameterized problem \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${L_2} \subseteq { \{ 0 , 1 \} ^*} \times \mathbb{N}$$ \end{document} is an algorithm that, on input \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( x , k ) \in { \{ 0 , 1 \} ^*} \times \mathbb{N}$$ \end{document} , outputs an instance \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( x ^{\prime} , k ^{\prime} ) \in { \{ 0 , 1 \} ^*} \times \mathbb{N}$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$f ( k ) \cdot poly ( \vert x \vert )$$ \end{document} time, for some fixed function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$f ( )$$ \end{document} and polynomial \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$poly ( )$$ \end{document} , satisfying:

-  \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( x , k ) \in {L_1} \leftrightarrow ( x ^{\prime} , k ^{\prime} ) \in {L_2}$$ \end{document} .

If L₁ reduces, as such, to L₂, and L₁ is W[1]-hard, then L₂ is W[1]-hard as well. It is widely believed that W[1]-hard problems are not FPT.

3.1. Three biclique problems

We next consider three possible candidates for biclique computation problems. For the sake of simplicity, we consider only decision problems for now. For a fixed positive integer d, a biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} is called a d-block biclique if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A ^{\prime} \subseteq A [ i , i + d ]$$ \end{document} for some \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$1 \le i \le n - d$$ \end{document} .

Bipartite Biclique:

Input: A bipartite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$G = ( A \uplus B , E )$$ \end{document} and an integer k.

Question: Is there a biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} in G with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert A ^{\prime} \vert \vert B ^{\prime} \vert \ge k$$ \end{document} ?

Bipartite Balanced Biclique:

Input: A bipartite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$G = ( A \uplus B , E )$$ \end{document} and an integer k.

Question: Is there is a biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} in G with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert A ^{\prime} \vert = \vert B ^{\prime} \vert \ge k$$ \end{document} ?

Block Bipartite Biclique:

Input: A bipartite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$G = ( A \uplus B , E )$$ \end{document} and two positive integers d and k.

Question: Is there a d-block biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} in G with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert A ^{\prime} \vert \vert B ^{\prime} \vert \ge k$$ \end{document} ?

Thus, the latter of these problems is tailor suited for the RAGB problem, but the other two might a priori be of use in this context as well. In Bipartite Biclique, we wish to find a biclique with at least k edges, and in Bipartite Balanced Biclique we wish to find a biclique where each side has at least k vertices. Solutions to both of these problems are clearly meaningful in our context. Note that we could have also considered a third variant where the goal is to find a biclique with k vertices altogether (i.e., on both sides), but in the setting of parameterized complexity of which we analyze all our problems, this problem is quite similar to Bipartite Biclique.

We first show that the Bipartite Biclique problem can be solved in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O{ ( 2^k}n )$$ \end{document} time, where k is the number of edges in the solution biclique, whereas the Balanced Bipartite Biclique problem is unlikely to have such an efficient algorithm. For the former result, we use the algorithm by Tanay et al. (2002), who showed that one can determine whether a bipartite graph G has a biclique with at least k edges in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O{ ( 2^ \varDelta } \cdot n )$$ \end{document} time, where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varDelta$$ \end{document} is the maximum A-degree of G; that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\varDelta = \mathop { \max } \nolimits_{a \in A} \vert N ( a ) \vert$$ \end{document} . This algorithm goes through each vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a \in A$$ \end{document} , and checks each subset \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B ^{\prime} \subseteq N ( a )$$ \end{document} of neighbors of a to determine whether for the set of common neighbors \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${A_{B ^{\prime} }}$$ \end{document} of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B ^{\prime}$$ \end{document} we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert {A_{B ^{\prime} }} \vert \vert B ^{\prime} \vert \ge k$$ \end{document} . The bound on the running time of this algorithm comes from the fact that there are at most \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${2^ \varDelta }$$ \end{document} such subsets \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B ^{\prime}$$ \end{document} for each vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a \in A$$ \end{document} .

The algorithm given earlier immediately implies that Bipartite Biclique is in FPT when parameterized by k along with the following observation: If there is a vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a \in A$$ \end{document} with at least k neighbors in B, then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( \{ a \} , N ( a ) )$$ \end{document} is a solution biclique. Thus, we can check in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( kn )$$ \end{document} time whether there is such a vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a \in A$$ \end{document} , and report “yes” if such a vertex is found. Otherwise, the maximum A-degree of our input bipartite graph is at most k, and we can apply the algorithm of Tanay et al. (2002).

Lemma 1. Bipartite Biclique can be solved in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O{ ( 2^k}n )$$ \end{document} time.

Lemma 2. Bipartite Balanced Biclique is W[1]-hard with respect to parameter k.

Proof. We deduce from the Biclique problem that was recently shown to be W[1]-hard by Lin (2015): Given a (not necessarily bipartite) graph H and a positive integer k (the parameter), determine whether G contains a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${K_{k , k}}$$ \end{document} (a biclique with k vertices on each side) as a subgraph. Given an instance \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( H = ( V , {E_H} ) , k )$$ \end{document} for the Biclique problem, we construct an instance \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( G = ( A \uplus B , E ) , k )$$ \end{document} for the Bipartite Biclique problem by letting A and B be two copies of V. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${a_v} \in A$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${b_v} \in B$$ \end{document} denote the two copies of vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$v \in V$$ \end{document} in G. We construct the set of edges of G by setting \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$E = \{ \{ {a_u} , {b_v} \} , \{ {a_v} , {b_u} \} : \{ u , v \} \in {E_H} \} $$ \end{document} .

Observe that any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${K_{k , k}}$$ \end{document} subgraph with sides V_A and V_B in H translates to a balanced biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( \{ {a_v} \in A:v \in {V_A} \} , \{ {b_v} \in B:v \in {V_B} \} )$$ \end{document} in G where each side has size k. Conversely, if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} is a balanced biclique in G with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert A ^{\prime} \vert = \vert B ^{\prime} \vert = k$$ \end{document} , then consider the sets \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${V_A} = \{ v \in V:{a_v} \in A ^{\prime} \} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${V_B} = \{ v \in V:{b_v} \in B ^{\prime} \} $$ \end{document} . Note that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${V_A} \cap {V_B} = \emptyset$$ \end{document} , since no vertex is adjacent to its copy in G. Moreover, by construction, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\{ u , v \} \in {E_H}$$ \end{document} for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$u \in {V_A}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$v \in {V_B}$$ \end{document} . It follows that V_A and V_B are two sides of a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${K_{k , k}}$$ \end{document} copy in H.■

Thus, the Bipartite Biclique problem is FPT with respect to parameter k, whereas Balanced Bipartite Biclique is not (under the widely believed assumption that FPT \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\ne$$ \end{document} W[1]). Note, however, that the main issue with the Bipartite Biclique problem is that we assume that the number of edges \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert A ^{\prime} \vert \vert B ^{\prime} \vert$$ \end{document} in a solution biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} will be rather small, and can thus be taken as a parameter. This is not the case for the Block Bipartite Biclique problem. As we will see in Subsection 3.2, this latter problem is FPT with respect to d, which for our purposes is much smaller than the number of edges in a solution biclique. Note that the biological motivation for RAGB1 and RAGB2 naturally yields small bounds on d, but not on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert A ^{\prime} \vert \vert B ^{\prime} \vert$$ \end{document} (see Section 1).

3.2. Solving RAGB1: an algorithm for computing d-block bicliques

The Block Bipartite Biclique problem trivially has a fixed parameter algorithm with respect to k, the number of edges in the solution biclique, by using the same arguments used in proving Lemma 1. We next show that this problem also has a fixed parameter tractable algorithm with respect to parameter d, the size of the block, which is expected to be much smaller in practice than k. In fact, we will show a much stronger result in that we can compute in FPT time the set of all maximal d-block bicliques of our input graph.

Lemma 3. Given a bipartite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$G = ( A \uplus B , E )$$ \end{document} with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert A \vert = n$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert B \vert = m$$ \end{document} , and an integer d, one can compute the set of all maximal d-block bicliques of G in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( nm + {2^d}nm / \lg m )$$ \end{document} time.

Algorithm for computing d-block bicliques:

- For each \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$i \in \{ 1 , \ldots , n - d \} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A ^{\prime} \subseteq A [ i , i + d ]$$ \end{document} do

Note that the set of all bicliques produced by this algorithm contains all maximal bicliques of G. These can be easily weeded out at a postprocessing stage, or during the computation of the algorithm.

To bound the running time of the algorithm cited earlier, first observe that we need \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( nm )$$ \end{document} time just to read the entire input. Next, notice that the algorithm has \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( n )$$ \end{document} iterations, where in each iteration it computes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${2^d}$$ \end{document} bicliques \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} . Starting in each iteration with bicliques \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert A ^{\prime} \vert = 1$$ \end{document} , and increasing the size of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A ^{\prime}$$ \end{document} by one each time, each set of common neighbors \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${B_{A ^{\prime} }}$$ \end{document} can be computed with a single set intersection operation between \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$N ( a ) \subseteq B$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${B_{A ^{\prime} \backslash \{ a \} }} \subseteq B$$ \end{document} for any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a \in A ^{\prime}$$ \end{document} . This set intersection operation can be naively performed in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( m )$$ \end{document} time, giving a total running time of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O{ ( 2^d}nm )$$ \end{document} to our algorithm. However, using standard bit-tricks of the RAM model, we can improve the running time of each such operation to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( m / \lg m )$$ \end{document} , reducing the total running time of our algorithm to the one stated in Lemma 3.

We consider each set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B ^{\prime} \subseteq B$$ \end{document} as a binary vector \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {B ^{\prime} } \in { \{ 0 , 1 \} ^m}$$ \end{document} , which is no more than the incidence vector of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B ^{\prime}$$ \end{document} in B (i.e., \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {B ^{\prime} } [ j ] = 1$$ \end{document} iff \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${b_j} \in B ^{\prime}$$ \end{document} ). Clearly, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {{B_1} \cap {B_2}}$$ \end{document} equals the bitwise AND between \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {{B_1}}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {{B_2}}$$ \end{document} . Since in the standard RAM model we can store each vector \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {B ^{\prime} }$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( m / \lg m )$$ \end{document} words, and as the bitwise AND operation between a pair of words can be computed in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( 1 )$$ \end{document} time in this model, it follows that we can compute \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {{B_1} \cap {B_2}}$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( m / \lg m )$$ \end{document} time. This reduces each common neighbors computation to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( m / \lg m )$$ \end{document} time, and gives us a total running time of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( nm + {2^d}nm / \lg m )$$ \end{document} for the entire algorithm.

3.3. Adapting RAGB to the weighted variant

We next show how to adapt our algorithm to the case where the edges of our input bipartite graph have weights, and we wish to store the total edge weight of each biclique for later evaluations. Thus, in this setting, we are provided with a weight function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$w:E \to \{ 1 , \ldots , x \} $$ \end{document} that assigns positive weights to the edges of our input bipartite graph G, and for each biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} in G, we wish to store the value \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$w ( A ^{\prime} , B ^{\prime} ) = \sum \nolimits_{a \in A ^{\prime} , b \in B ^{\prime} } w ( a , b )$$ \end{document} . Later, we show how to adapt our algorithm from the previous section to handle this case as well. To do this, we assume that x is a fixed (relatively small) constant.

Note that the naive adaptation of our algorithm is to compute the weight of each new biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} in a straightforward manner, that is, by summing up all the weights on the edges in the biclique. This would take \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( dm )$$ \end{document} time for each biclique, and it would raise the complexity of the algorithm to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O{ ( 2^d}dnm )$$ \end{document} time. A better way to do this is as follows: For each \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A ^{\prime} \subseteq A$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$b \in B ^{\prime}$$ \end{document} , define \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${w_{A ^{\prime} }} ( b )$$ \end{document} to be the sum \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${w_{A ^{\prime} }} ( b ) = \sum \nolimits_{a \in A ^{\prime} } w ( a , b )$$ \end{document} . Then, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$w ( A ^{\prime} , B ^{\prime} ) = \sum \nolimits_{b \in B ^{\prime} } {w_{A ^{\prime} }} ( b )$$ \end{document} for each biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} . This equality allows us to obtain a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( d \lg m / \lg d )$$ \end{document} speedup as explained next.

Similar to the previous section, we represent the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B ^{\prime}$$ \end{document} of each biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} by a vector \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {B ^{\prime} }$$ \end{document} , except that here \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {B ^{\prime} }$$ \end{document} will be a vector in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \{ 0 , \ldots , dx \} ^m}$$ \end{document} , where the j'th entry of this vector will equal \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${w_{A ^{\prime} }} ( {b_j} )$$ \end{document} . Here, it is important to note that since each d-block biclique has at most d vertices belonging to A, and since the maximum edge weight is x, we know that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${w_{A ^{\prime} }} ( b ) \le xd$$ \end{document} for any biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} and any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$b \in B ^{\prime}$$ \end{document} . Now, we wish to compute, given two vertex subsets \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${B_1} , {B_2} \subseteq B$$ \end{document} , the vector \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {{B_0}} = \overrightarrow {{B_1}} \oplus \overrightarrow {{B_1}}$$ \end{document} defined by a component-wise operation \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\oplus$$ \end{document} , that is, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {{B_2}} [ j ] = \overrightarrow {{B_0}} [ j ] \oplus \overrightarrow {{B_2}} [ j ]$$ \end{document} for each \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$j \in \{ 1 , \ldots , m \} $$ \end{document} , where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \overrightarrow {{B_1}} [ j ] \oplus \overrightarrow {{B_2}} [ j ] = \left( { \begin{matrix} { \overrightarrow {{B_1}} [ j ] + \overrightarrow {{B_2}} [ j ] } \hfill & {{ \rm{if}} \ \overrightarrow {{B_1}} [ j ] , \overrightarrow {{B_2}} [ j ] \ne 0 , } \hfill \\ 0 \hfill & {{ \rm{otherwise}}.} \hfill \\ \end{matrix} } \right. \end{align*} \end{document}

Note that in this way, computing the vector \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {B ^{\prime} }$$ \end{document} of some biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B )$$ \end{document} reduces to computing a single \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\oplus$$ \end{document} operation between \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {N ( a ) }$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {{B_{A ^{\prime} \backslash \{ a \} }}}$$ \end{document} for some \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$a \in A ^{\prime}$$ \end{document} , as explained in the previous section. This can be easily done in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( m )$$ \end{document} time, but because this vector operation is defined as a component-wise operation we can apply the “Four Russians” trick (Angluin, 1976) to gain an extra speedup.

Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$y = \frac { 1 } { 4 } \cdot \mathop { \log } \nolimits_ { dx + 1 } ( m )$$ \end{document} , and assume that both y and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$m / y$$ \end{document} are integers (otherwise, we can add at most \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( m )$$ \end{document} dummy isolated vertices to B for these two quantities to become integers). Each vector in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \{ 0 , \ldots , dx \} ^m}$$ \end{document} is cut into \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$m / y$$ \end{document} pieces, where each piece is a vector in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \{ 0 , 1 \ldots , x \} ^y}$$ \end{document} . Now note that there are \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ ( dx + 1 ) ^{2y}} = \sqrt m$$ \end{document} possible different pairs of pieces altogether. This means that we can compute in an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( \sqrt m \cdot y ) = O ( m )$$ \end{document} time preprocessing step, an auxiliary table that stores the piece \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {{P_1}} \otimes \overrightarrow {{P_2}}$$ \end{document} for every possible pair \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {{P_1}} , \overrightarrow {{P_2}} \in { \{ 0 , 1 , \ldots , dx \} ^y}$$ \end{document} . Using this table, we can compute the pieces of the vector \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {{B_1}} \oplus \overrightarrow {{B_2}}$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( m / y ) = O ( m \lg d / \log m )$$ \end{document} time, for any pair of vectors \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\overrightarrow {{B_1}} , \overrightarrow {{B_2}} \in { \{ 0 , \ldots , dx \} ^m}$$ \end{document} . This allows us to reduce the computation of the total weight of each biclique to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( m \lg d / \log m )$$ \end{document} time, giving us a total run time of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( nm + {2^d} \lg d \cdot nm / \log m )$$ \end{document} for the entire algorithm.

3.4. Solving RAGB2: the colorful variant

For the purposes of solving RAGB2, we consider the colorful variant of the Block Bipartite Biclique problem where the vertices in B have colors, and we wish to find a biclique that contains at most one vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$b \in B$$ \end{document} of each color. For this purpose, let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c:B \to \{ 1 , \ldots , C \} $$ \end{document} be a coloring function of the vertices in B. Recall that a biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} is said to be colorful if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c ( {b_1} ) = c ( {b_2} )$$ \end{document} implies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${b_1} = {b_2}$$ \end{document} , for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${b_1} , {b_2} \in B ^{\prime}$$ \end{document} . The Colorful Block Bipartite Biclique problem is the variant of Block Bipartite Biclique, where we wish to find a colorful block biclique with a certain number of edges.

Unfortunately, we can no longer apply dynamic programming and the four Russians trick in this case. This is because the colors make the problem harder to handle. In fact, it turns out that the colorful variants of the two other bipartite biclique problems discussed earlier are W[1]-hard. This is not surprising for Colorful Balanced Bipartite Biclique, as Balanced Bipartite Biclique is W[1]-hard by Lemma 2, and there is a generic parameterized reduction from any problem to its colorful variant using the color-coding technique (Alon et al., 1995). For Colorful Bipartite Biclique, we need a slightly more elaborate argument:

Lemma 4. Colorful Bipartite Biclique is W[1]-hard when parameterized by k.

Proof. We deduce from the Multicolored Clique problem: Given a k-partite graph G with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V ( G ) = {V_1} \uplus {V_2} \uplus \cdots \uplus {V_k}$$ \end{document} , determine whether G contains a clique, including one vertex from each V_i. In Fellows et al. (2009), it is shown that this problem is W[1]-hard when parameterized by k. Given such a graph G as an instance to Multicolored Clique, we construct an instance \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( H , c , k )$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$H = ( A \uplus B , E )$$ \end{document} , to the Colorful Bipartite Biclique problem by letting A and B be two copies of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$V ( G )$$ \end{document} . Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${a_v} \in A$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${b_v} \in B$$ \end{document} denote the two copies of the vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$v \in V ( G )$$ \end{document} in H. We construct the set of edges of H by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$E = \{ \{ {a_u} , {b_v} \} : \{ u , v \} \in E ( G ) \} \cup \{ \{ {a_v} , {b_v}:v \in V ( G ) \} $$ \end{document} . Finally, we define the coloring function \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c:A \to \{ 1 , \ldots , k \} $$ \end{document} by setting \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$f ( {a_v} ) = i \leftrightarrow v \in {V_i}$$ \end{document} , and we let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\ell = \left( { \begin{matrix} k \\ 2 \\ \end{matrix} } \right)$$ \end{document} .

Observe that any multicolored clique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${v_1} , \ldots , {v_k}$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${V_i} \in {V_i}$$ \end{document} in G defines a multicolored biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} in H with \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A ^{\prime} = \{ {a_{{v_i}}}:1 \le i \le k \} $$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B ^{\prime} = \{ {b_{{v_i}}}:1 \le i \le k \} $$ \end{document} that has exactly \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\ell = \left( { \begin{matrix} k \\ 2 \\ \end{matrix} } \right)$$ \end{document} edges. Conversely, let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} denote a multicolored biclique in H with at least \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\left( { \begin{matrix} k \\ 2 \\ \end{matrix} } \right)$$ \end{document} edges. Then, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert A ^{\prime} \vert = k$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert B ^{\prime} \vert \ge k$$ \end{document} . Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${a_i} \in A$$ \end{document} denote the vertex of A with color i, and let v_i denote the vertex of G corresponding to a_i. Then, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${v_i} \in {V_i}$$ \end{document} for each i. Now, note that for each color i, there can be at most one vertex in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B ^{\prime}$$ \end{document} , which is a copy of a vertex in V_i, since a_i is only adjacent to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${b_{{v_i}}}$$ \end{document} among vertices in B corresponding to vertices of V_i. Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert B \vert \ge k$$ \end{document} , it follows that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\vert B \vert = k$$ \end{document} , and there is a unique vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${b_i} \in B ^{\prime}$$ \end{document} , which is a copy of a vertex in V_i. According to what has been just cited, this vertex must be v_i, and so \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A ^{\prime}$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B ^{\prime}$$ \end{document} correspond to the same k vertices \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${v_1} , \ldots , {v_k}$$ \end{document} in G. As \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} is a biclique, this implies by construction that any pair of distinct vertices in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${v_1} , \ldots , {v_k}$$ \end{document} are adjacent in G, implying that G has a multicolored clique of size k.    ■

Regardless of what has been just cited, we can still compute in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( m )$$ \end{document} time a maximum-sized subset \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$B ^{\prime} \subseteq {B_{A ^{\prime} }}$$ \end{document} in a set of common neighbors of some \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A ^{\prime} \subseteq A$$ \end{document} . This means that we can adapt the algorithm cited earlier to compute the maximum-sized colorful biclique \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O ( m )$$ \end{document} time per biclique. Moreover, note that in the same amount of time we can actually count the number of different colorful bicliques \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( A ^{\prime} , B ^{\prime} )$$ \end{document} corresponding to some \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$A ^{\prime} \subseteq A [ i , i + d ]$$ \end{document} . This is done by a simple combinatorial computation that considers all possibilities of picking a single vertex out of each color in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${B_{A ^{\prime} }}$$ \end{document} .

Lemma 5. Colorful Block Bipartite Biclique can be solved in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$O{ ( 2^d}nm )$$ \end{document} time.

4.1. Implementation of the main search engine

In this section, we describe the main search engine, corresponding to stages A and B of the pipeline illustrated in Figure 2. Given a reference query genome and a set of target genomes, in GenBank file format, the program first BLASTs each gene from the reference genome against each gene from the target genomes (using Blastall version 2.2.26), and it considers the two genes to be homologous if their BLAST score is below a predefined threshold h. On a successful BLAST result, genes from the target genome are re-labeled with the gene id of the corresponding gene from the reference element. If a gene in a target genome is found to be orthologous with more than one gene from the reference genome, we map it to the one with the highest BLAST score. Genes from the reference genome, on the other hand, could be mapped to more than one target gene in each target genome. For each target genome, a sequence of gene ids is then created, consisting only of the genes that were labeled by an ortholog from the reference element genes, and preserving the gene order in the original target genome.

Our program also takes as an input several parameters: an upper bound d (measured as number of genes) on the length of an interval in the reference query, a quorum q₁ on the minimal number of genes in a reference genome interval, and a quorum q₂ on the number of genomes required in a block. For segmenting the target genomes into intervals, biological segmentation is applied: The distance between two consecutive genes in an interval is bounded from above by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$max \_gap$$ \end{document} , which is a predefined constant. Our program computes a ranking score for each d-block, reflecting its probabilistic likelihood (see Section 4.2). A user-defined filtration parameter, denoted \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$min \_score$$ \end{document} , is used to bound from below the score of any d-block accepted as output by our program.

4.2. Ranking score computation

Let m denote the number of genomes, and let n denote the length of each of these genomes. We define our ranking score as the probability that k genes appear together in d-blocks of at least c out of the m genomes. We denote the probability of this event by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Pr [ k , d , c ]$$ \end{document} . Here, we assume that each genome is a permutation on \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\{ 1 , \ldots , n \} $$ \end{document} drawn uniformly and independently at random.

Lemma 6. The following bound holds: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} { \rm Pr } [ k , d , c ] \le \mathop \sum \limits_ { i = c } ^m \left( { \left( { \begin{matrix} m \\ i \\ \end {matrix} } \right) { { \left( { { \frac { \left( { \begin {matrix} { n - k } \\ { d - k } \\ \end {matrix} } \right) } { \left( { \begin {matrix} n \\ d \\ \end {matrix} } \right) } } ( n - d ) } \right) } ^i } { \,\, { \left( { 1 - \left( { { \frac { \left( { \begin {matrix} { n - k } \\ { d - k } \\ \end {matrix} } \right) } { \left( { \begin {matrix} n \\ d \\ \end {matrix} } \right) } } ( n - d ) } \right) } \right) } ^ { m - i } } } \, \right). \end{align*} \end{document}

Proof. Fix some k genes and some d-block i of some genome g, and let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \mathcal{E}_{k , i}}$$ \end{document} denote the event that these genes appear in this d-block of g. Then, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $Pr [ { \mathcal{E}_i} ] = \left( { \begin{matrix} {n - k} \\ {d - k} \\ \end{matrix} } \right) \bigg/ \left( { \begin{matrix} n \\ d \\ \end{matrix} } \right)$ \end{document} , since g is a random permutation picked uniformly at random. Since there are \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( n - d )$$ \end{document} different d-blocks in g, by union bound we get that the probability of the event that these genes appear in any d-block of g, denoted \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \mathcal{E}_d}$$ \end{document} , is bounded by

Now, let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${ \mathcal{E}_{d , c}}$$ \end{document} denote the event that these k genes appear in d-blocks of some specific set of c genes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${g_1} , \ldots , {g_c}$$ \end{document} . Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${g_1} , \ldots , {g_c}$$ \end{document} are picked independently at random, we have \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} { \rm Pr } [ { \mathcal { E } _ { d , c } } ] = ( Pr [ { \mathcal { E } _d } { ] ) ^c } \le { \left( { { \frac { \left( { \begin {matrix} { n - k } \\ { d - k } \\ \end {matrix} } \right) } { \left( { \begin {matrix} n \\ d \\ \end {matrix} } \right) } } ( n - d ) } \right) ^ { c } } . \end{align*} \end{document}

The probability that these k genes appear in at least \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$c \le m$$ \end{document} genomes is then bounded by \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} \begin{align*} \mathop \sum \limits_ { i = c } ^m \left( { \left( { \begin {matrix} m \\ i \\ \end {matrix} } \right) { { \left( { { \frac { \left( { \begin {matrix} { n - k } \\ { d - k } \\ \end {matrix} } \right) } { \left( { \begin {matrix} n \\ d \\ \end {matrix} } \right) } } ( n - d ) } \right) } ^i } { \,\, { \left( { 1 - \left( { { \frac { \left( { \begin {matrix} { n - k } \\ { d - k } \\ \end {matrix} } \right) } { \left( { \begin {matrix} n \\ d \\ \end {matrix} } \right) } } ( n - d ) } \right) } \right) } ^ { m - i } } } \right) , \end{align*} \end{document}

and the lemma thus holds.

Each component in the sum given in Lemma 6 can be extremely small. Therefore, we use logarithms instead, so that the numbers become manageable. Further, to speed up the computation, we actually compute an upper bound for this sum, by computing the value of the maximum term and then multiplying it by the total number of terms. Throughout the remainder of this article, we use P for short to denote our ranking score.

4.3. A pipeline for gene block postprocessing and visualization

The output of stage B of the RAGB Monitor pipeline consists of all the filtration-surviving d-blocks, annotated with the corresponding ranking scores, where each block consists of a gene set and the corresponding homologous instances of the gene set, confined to genomic segments in target genomes. For each instance of a block in a target genome, our program keeps track of the block's consensus gene set, as well as all other genes in the same genomic segment that are homologous to any of the genes from the query. This information is used for block visualization and for further interpretation of its instances (see examples in Section 5).

The number of blocks identified by our algorithm grows exponentially with respect to parameter d. Therefore, we developed a postprocessing pipeline, where we filter the results and organize them into families of related blocks. The block postprocessing and visualization pipeline is composed of six steps, as illustrated in Figure 2C: Step 1 receives all blocks identified by the search engine, filtered by the predefined quorums and ranking score threshold. Next, in Step 2 of the pipeline, a graph is constructed where each block is represented by a node, and in which an edge connects two nodes if the number of genes shared by the gene sets of the corresponding blocks exceeds a predefined threshold t₁. In Step 3 of the pipeline, the families of related gene blocks are identified as cliques in the graph constructed in Step 2. Maximal cliques are computed via the findcliques procedure (Bron and Kerbosch, 1973; Cazals and Karande, 2008), implemented as part of the NetworkX (Schult and Swart, 2008) Python package.

The block families identified in Step 3 of the pipeline are often redundant, in the sense that distinct families share similar gene blocks. This redundancy is handled in Steps 4 and 5 of the pipeline. In Step 4, another graph is constructed, where each block family computed in Step 3 is represented by a node, and in which an edge connects two nodes if the number of genes shared by the gene sets of the corresponding families exceeds a predefined threshold t₂. Then, in Step 5, similar block families are identified as cliques in the graph constructed in Step 4 of the pipeline. From each such clique, only one representative gene block family is reported in the output: the family containing the largest gene set among all the families participating in the clique. In Step 6, the selected gene families with their corresponding gene blocks are reported, sorted by their ranking score, where each gene block family is assigned the score of its highest scoring gene block.

To further clarify the visualization of the results, we also color the instances of each block according to an instance homology measure reflecting the composition, order, and direction of the genes participating in the instance. This process is described in the next section.

4.4. Instance coloring per block

Recall that all genomic instances of a given block contain the genes from the consensus gene set characterizing the block, and that distinct instances of the same block could differ by the order of the block's consensus genes within the instance and by the composition and order of the additional intermitting genes. To obtain a more specific functional and evolutionary interpretation of an output gene block and to sharpen the visualization of its target instances, we apply a comparative coloring scheme to the instances of each block. According to this coloring scheme, instances of a block are assigned the same color if they are highly similar in terms of their gene content, and if their genes maintain collinear order and similar direction.

Figure 3 illustrates the approach employed by our program for instance coloring. To cluster the distinct instances of a block to homologous instance groups, we apply an algorithm that takes as input a pair of ordered gene sequences representing the gene sets of the two distinct instances, and compares them via an edit distance measure. The edit distance algorithm computes the least-cost transformation from one gene sequence to the other, where the allowed transformation operations are gene direction inversions, insertions, deletions, and substitutions. In our implementation, all edit operations are assigned a cost of 1 except for the direction inversion operation, which is assigned a cost of 0.5. Based on this edit distance measure, all-pairs distances are computed for all target instances of the block, resulting in a matrix of pairwise distances, to which a clustering algorithm is applied. Each of the resulting clusters is then assigned a distinct color, and the corresponding instances are colored accordingly by the visualization program. For clustering, we used DBSCAN (Ester et al., 1996; Pedregosa et al., 2011) (A Density-Based Spatial Clustering Algorithm that does not require the user to specify the number of sought clusters in advance). The DBSCAN algorithm entails the setting of two additional parameters: Eps, the maximum radius of the neighborhood, and MinPts, the minimum number of points in the Eps-neighborhood of a point. These are set differently according to the specific application at hand (see Section 5).

OPEN IN VIEWER

FIG. 3.

Coloring the instances of a gene block according to a homology measure that takes into account gene composition, gene direction, and the collinear order of genes within the instances. (A) An input gene block. (B) Computation of an all-pairs distance matrix of the block instances. (C) Application of a clustering algorithm to the all-pairs distance matrix, yielding a coloring of the block instances, where homologous instances are assigned the same color.

4.5. Measuring running times versus increasing window sizes

The exponential factor in the theoretical analysis of our algorithm is the bound on window size (parameter d). We measured the effect of this parameter on the practical running time of our program. For this, we needed to employ long queries, and thus extracted 99 plasmids from the VFDB database (Chen et al., 2005), with an average length of 104 genes per plasmid. First, we executed our program on all the plasmids, setting window size \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d = 17$$ \end{document} . Then, we selected for our test the top scoring 25 plasmids (i.e., those that required the most extensive interrogation by the search algorithm), each of which yielded at least one block with a minimum P score of 20. For those plasmids, we executed the RAGB-Monitor program with running window lengths from 2 to 24, measured the corresponding running times, and computed the average across all plasmids in the test set. The results are shown in Figure 4.

OPEN IN VIEWER

FIG. 4.

RAGB-Monitor running times (in seconds) versus increasing window sizes, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d = 2 \ldots 24$$ \end{document} .

5.1. A benchmark of 558 GIs versus 33 target genomes

The input to our pipeline consists of the query island Q and the set of target genomes \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${T_1} \cdots {T_c}$$ \end{document} . For the target genomes, we used 33 genomes of proteobacteria that were downloaded from NCBI, as described in Ream et al. (2015), who used this set of genomes in a study of the evolution of Escherichia coli operons.

For the queries (i.e., reference genomes), we used GIs that were found in the 33 target genomes. For this, we used a benchmark set of distinct GIs that were extracted from the IslandViewer 3 (Dhillon et al., 2015) database, a web-based resource that incorporates three GI prediction methods: SIGI-HMM, IslandPath-DIMOB, and IslandPick (Hsiao et al., 2003; Waack et al., 2006; Langille et al., 2008). The first two methods are sequence composition-based approaches that do not rely on cross-species conservation. SIGI-HMM discovers codon usage bias via a Hidden Markov Model approach, whereas Island-PathDIMOB measures dinucleotide bias and seeks the presence of associated mobility genes (integrases, transposases, etc.) to identify possible GIs. On the other hand, IslandPick uses a comparative genomics-based approach, identifying unique regions by comparing a user-specified genome against closely related genomes. For the sake of avoiding GIs that were identified by comparative genomics-based methods, which is the main approach in our algorithm, we extracted from the IslandViewer database only those islands that were discovered by at least one of the composition-based approaches (SIGI-HMM and IslandPath-DIMOB) and avoided those islands that were predicted by approaches that employ cross-genome conservation criteria in their GI search (IslandPick). We excluded from the benchmark five of the predicted GIs that consisted of long cassets of Ribosomal genes, as this well-studied operon occurs in all prokaryotic genomes and is not transferred horizontally (Jain et al., 1999). This yielded a total of 558 distinct GIs. All the query GIs and target genomes participating in our benchmarks, as well as the results, are given in: https://ragbimonitor-7614a.firebaseapp.com/#/about.

When setting the search engine parameters \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$d = 16 , {q_1} = 5 , {q_2} = 3 , h = 0.01$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$max \_gap = 2000$$ \end{document} , the application of RAGB monitor to data mine the 558 predicted GIs versus the 33 target genomes took 3936 seconds to run on an Intel Xeon X5680 machine with 192 GB RAM (Note that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$h = 0.01$$ \end{document} is considered a rather loose BLAST threshold for the general task of identifying orthologous genes; however, in our application, evidence for orthology is strengthened by the genomic context of conserved gene blocks). For the postprocessing pipeline, we set the score threshold \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$min \_score = 40$$ \end{document} , and the parameters \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${t_2} = 0.75$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $${t_1} = 2$$ \end{document} , \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Eps = 0$$ \end{document} , and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$minPTl = 2$$ \end{document} (these parameters are explained in Section 4.3).

Note that our goal in this section is not to propose a new approach for the prediction pathogenicity islands, but rather to exemplify how our tool could be used to identify, visualize, and study the distribution of putatively mobilized operons that are highly abundant in the target genomes. To clear out some of the noise due to false-positive GI predictions with core-genome operons, we required that in each block family surviving the filtration criterion, at least one of its blocks be found in two distinct instances within the same species. This yielded the 38 results shown in Table 1, and on our website we give both the filtered and the unfiltered results.

One of the most abundant pathways among the results was type III secretion system (T3SS), identified in 5 out of the 38 results. In the next section, we analyze one of these T3SS gene block results in detail.

5.2. Detailed example: a T3SS gene block based on a Bordetella pertussis GI query

One of the most exciting developments in the field of bacterial pathogenesis in recent years is the discovery that many pathogens utilize complex nanomachines to deliver bacterially encoded effector proteins into target eukaryotic cells. These effector proteins modulate a variety of cellular functions in the animal or plant hosts and manipulate them for the pathogen's benefit. One of these protein-delivery machines is the T3SS (Hueck, 1998; Wagner et al., 2010). T3SSs are widespread in nature and are encoded not only by bacteria that are pathogenic to vertebrates or plants but also by bacteria that are symbiotic to plants or insects (Büttner and He, 2009; Correa et al., 2012). Although the secretion machine is highly conserved across bacterial species, the effector proteins that they deliver are specific for each individual pathogen or symbiont that encodes them (Galán, 2009). A central component of T3SSs is the needle complex (also denoted “injectosome”), a supramolecular structure that mediates the passage of the secreted proteins across the bacterial envelope. Working in conjunction with several cytoplasmic components, the needle complex engages specific substrates in sequential order, moves them across the bacterial envelope, and ultimately delivers them into eukaryotic cells. The central role of T3SSs in pathogenesis makes them great targets for novel antimicrobial drug strategies.

Recent phylogenetic analyses support the notion that T3SSs are an evolutionary exaptation of the flagellar apparatus (Pallen et al., 2005), a rotating filament used in chemotaxis. The evolutionary process may have proceeded in two steps (Abby and Rocha, 2012). The first step, the descendants of which can still be detected in Myxococcales (Konovalova et al., 2010), began with an early flagellar operon (sctFJLNQRSTUV) separating from the other flagellar genes, and led to a structure that is competent for protein secretion although it is no longer able to carry out motility functions. The second step, which may have occurred more than once, involved a series of genetic deletions and recruitments of components from other cellular structures (based mainly on a family of outer-membrane proteins, denoted secretins, that are involved in phage release or protein secretion). Their evolutionary analysis suggests that the injectosome then quickly adapted to different eukaryotic cells while maintaining a core structure that remains highly similar to the flagellum.

Although the T3SS and flagellar apparatus machineries clearly differ in both overall structure and function, at their core, they both consist of a conserved machinery for protein export (Fig. 5). In the flagellum, this common machinery is used to export the distal flagellar components and build the extracellular filament. Within the T3SS, the common complex is at the center of the export machinery and enables both the formation of the extracellular needle and the direct transfer of substrates from the bacterial cytosol into the host cells. Sequence homologies exist between genes of T3SSs and those genes of the flagellar assembly pathway participating in the conserved machinery for protein export (Erhardt et al., 2010). Note that each model of T3SS and flagellar genes has its unique nomenclature in the literature. Hence, we use a unifying nomenclature throughout this section, where prefixes fli and flh denote flagellar genes, and prefix sct denotes T3SS genes. Table 2 gives the name mapping between pairs of homologous genes across flagellar apparatus versus T3SS system pathways, to be used throughout this section. As you follow the example given in this section and the corresponding illustrations, please note that the reference genomes and block instances illustrated in the figures could be directed either way (left to right or right to left, depending on the strand in which the instance was found). However, when naming the gene blocks and the corresponding operons within the text, we consistently use alphabetically increasing order, as standard.

OPEN IN VIEWER

FIG. 5.

Flagellar apparatus machine versus T3SS Injectosome machine and their common core components. Figure prepared according to Diepold and Armitage (2015). HM, host membrane; IM, inner membrane; OM, outer membrane; PP, periplasm; T3SS, type III secretion system.

Our exemplifying result is based on a Bordetella pertussis Tomaha query GI (NC_002929-2362220-2378667), harboring the T3SS genes sctIJKLNOPQRSTUWC. This query yielded a single result family, consisting of 12 blocks. Figure 6 illustrates the three highest scoring blocks in the family. Note that the reference query GI was almost fully conserved in all three Bordetella genomes.

OPEN IN VIEWER

FIG. 6.

The three highest scoring blocks from Bordetella pertussis Tomaha query GI (NC_002929-2362220-2378667), consisting of type III secretion system and Flagellar Biosynthesis gene loci. At the top part of the figure, the query GI yielding these results is shown, and genes participating in the illustrated gene blocks are annotated with their gene names according to the nomenclature given in Table 2. The only genes shown in this illustration are the query genes and their homologs within block instances found in target genomes.

Block 1. The consensus gene set of the first block ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P = 100.37$$ \end{document} ) consists of six T3SS genes, sctNQRSTU, versus 10 target instances of these genes, spanning 10 \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\alpha , \beta$$ \end{document} , and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\gamma$$ \end{document} proteobacterial genomes. Note that all target instances of this block correspond to T3SS genes (This is not surprising, as the instance of this block within the query GI also consists of T3SS genes).

Block 2. The second block ( \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$P = 91.71$$ \end{document} ) consists of five query genes, sctQRSTU, versus 15 loci instances identified within 12 target genomes. Note that the second block shown in Figure 6 differs from the first block by the exclusion of the T3SS gene sctN from its gene set. Indeed, all 10 T3SS instances exposed by the first block remain exposed in the second block. In addition, there are five new target gene loci instances exposed in this block. A zoom-in on the contents of the block (Fig. 7) shows that all of these five new gene-loci instances (colored in pink) consist of flagellar apparatus genes, fliNPQRflhB (corresponding to their homologous T3SS genes sctQRSTU in the query gene set). Among the five instances of flagellar genes exposed in the second block, three are secondary instance hits within genomes where a T3SS gene loci was already exposed in the first block (Chromobacterium violceum, Pseudomonas auroginosa, and Pseudomonas sirengea). Interestingly, the homology between this flagellar apparatus operon and the corresponding Bordetella GI T3SS query genes was not high enough to expose any flagellar apparatus instances within the Bordetella target genomes. This observation could serve as additional evidence to the fact that T3SS is, indeed, horizontally transferred by pathogenicity islands (Schmidt and Hensel, 2004) (Fig. 7).

OPEN IN VIEWER

FIG. 7.

A zoom-in on the contents of the second block from Figure 6. The instance coloring for this figure is based on setting the edit-distance-based clustering parameters to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Eps = 0$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$MinPts = 0$$ \end{document} . The only genes shown in the illustration are the query genes and their homologs within the corresponding block instance segments. This figure continues the example of Figure 6. The block's consensus genes are T3SS system genes in the reference genome; whereas their homologous genes in the target genomes implement flagellar apparatus genes in the pink instances, and T3SS system genes in all the other target genome instances.

To better understand the overlapping conservation between the T3SS gene set sctQRSTU and their homologous flagellar genes, we turn to literature regarding the structural organizations of these genes. A thorough phylogenetic study of the operons of the flagellar apparatus across proteobacteria is given in Liu and Ochman (2007). According to Liu and Ochman, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\beta$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\gamma$$ \end{document} proteobacteria carry variations of the well-conserved operon fliMNOPQR. Employing Table 2 to decipher the homology between the T3SS and the corresponding flagellar genes, we observe that the second block's gene set, sctQRSTU, maps to the conserved flagellar operon, fliMNOPQR, as follows: The gene fliO from the conserved flagellar operon does not have a homolog in T3SS and, therefore, does not participate in the second block. The flagellar genes fliMN map to the T3SS gene SctQ, and the flagellar genes fliPQR map to the three T3SS genes sctRST. This covers all of the genes from the second block's gene set, except for SctU, which is the T3SS homolog of the flagellar gene flhA. This gene is, in general, conserved in the same operon with flhB in beta and gamma proteobacteria. However, in those species where the flagellar instance was exposed in the second block, flhA is clustered within the vicinity of fliMNOPQR. The reason that flhB does not show in the block is that its T3SS homolog, sctV, is not part of the query.

So how does the exclusion of sctN (FliI) from the consensus gene set sctNQRSTU of the first block explain the exposure of the five flagellar biosynthesis gene instances in the second block? The flagellar homolog of sctN is fliI, and according to Liu and Ochman (2007), this gene participates in another, dissociated operon, fliFGHIJKL, which is also well conserved in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\beta$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\gamma$$ \end{document} proteobacteria. This could possibly explain why the first block, in which sctN is included in the query gene set, did not expose any homologous flagellar loci instances, whereas the second block, which excludes this gene, exposed five flagellar gene loci.

A final observation regarding the second block is that no flagellar gene loci were exposed within the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\alpha$$ \end{document} nor the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$\epsilon$$ \end{document} proteobacteria target genomes. This is explained by the fact that, according to Liu and Ochman (2007), flagellar apparatus operons are most extensively disrupted in both of these proteobacterial classes, where the dissociated flagellar genes are transcribed in single or pair units.

Block 3. The third block \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$( P = 89.163 )$$ \end{document} from Figure 6 consists of eight query genes, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$sctJNQRSTUC ,$$ \end{document} versus 12 target genomes. Similar to the first block, all 12 instances matching the query are T3SS gene loci (Fig. 8). This is due to the fact that the T3SS gene sctC, encoding for the OM secretin ring, has no homolog among the flagellar biosynthesis genes. In addition, sctJ and sctN are homologous to the flagellar genes fliF and fliI, correspondingly, which according to Liu and Ochman (2007) are dissociated from the conserved flagellar biosynthesis operon containing sctQRSTU homologs.

OPEN IN VIEWER

FIG. 8.

A zoom-in on the contents of the third block from Figure 6. The instance coloring for this figure is based on setting the edit-distance-based clustering parameters to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$Eps = 0$$ \end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$MinPts = 0$$ \end{document} . The only genes shown in the illustration are the query genes and their homologs within the block instances. The consensus gene set of this block extends that of the second block in the family by three genes: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document} $$sctJ , sctN$$ \end{document} , and sctC. This block's consensus set consists of T3SS genes from the reference genome, and all their homologs within the target genome instances are also T3SS genes. Note that two of the additional genes sctJ and sctC are not collinearly order-conserved across the discovered instances, in contrast to the other genes, sctNQRSTU from the consensus gene set of this block, which are collinearly order-conserved in all instances.

A zoom-in on the third block (Fig. 8) illustrates that two of the genes in this block (sctC and sctJ) vary in their order and direction, with respect to the other genes from the same locus, across distinct instances of the block. This is a good illustration of the fact that our engine identifies flexible instances of conserved gene clusters, allowing gene order shuffling and inverted gene direction.