# Construct neighbourhood relation graph for n sequences

Given $$n$$ sequences with length $$m$$, $$s_i=\langle c_1^ic_2^i\dots c_m^i\rangle, i = 1,\dots, n$$, where $$c^i_j\in D$$ is a partial ordered set and the partial order relation $$\sqsubseteq$$ on $$D$$ answers any query $$x\sqsubseteq y$$ in constant time.

We define the neighbourhood relation over $$\{s_i\}$$ as:

For any $$\pi=\langle c_i \rangle \in \{s_i\},\tau=\langle c'_i \rangle \in \{s_i\}$$, $$\pi$$ and $$\tau$$ are neighbours if and only if: (1) $$\exists j$$, $$\neg(c_j\sqsubseteq c'_j)\lor\neg(c'_j\sqsubseteq c_j)$$, and (2) $$\forall i\neq j, c_i\sqsubseteq c'_i$$ or $$c'_i\sqsubseteq c_i$$. The neighborhood relation is denoted as $$\pi \sim \tau$$.

An example is taking $$=$$ as $$\sqsubseteq$$, then $$\pi\sim \tau$$ means $$\pi$$ and $$\tau$$ have exactly one different item.

Another example is taking a flatten join-semilattice as $$D$$, then $$\pi\sim\tau$$ means $$\pi$$ and $$\tau$$ has at least one different item and all different item pairs of $$\pi$$ and $$\tau$$ contains at least one $$\top$$ except for one pair.

Now consider the undirected graph $$G=(V, E)$$, where $$v_i \in V$$ represent $$s_i$$, and $$(v_i, v_j)\in E$$ if and only if $$s_i\sim s_j$$.

Since for any two sequence $$s_i, s_j$$, $$s_i\sim s_j$$ needs $$O(m)$$ query of $$\sqsubseteq$$ and $$\sqsubseteq$$ takes constant time, the complexity of judging $$s_i,s_j$$ is $$O(m)$$, and there are $$O(n^2)$$ pair of $$s_i,s_j$$, the total complexity is $$O(mn^2)$$.

Is there an algorithm for computing $$G$$ with better time complexity?

My initial effort is to consider given three sequence $$s_i,s_j,s_k$$, there seems does not exist an algorithm taking less than $$3\times 2m$$ query of $$\sqsubseteq$$, so the total complexity cannot be less than $$O(mn^2)$$, but I cannot prove it.