In this research we introduce the problem of the binary matrix partitioning in a biological context. Our idea is to use SNP matrix to construct a set of phylogenetic networks to retrieve underlying biological meanings and dependencies. We emphasize stochastic methods for matrix clustering and briefly describe the search algorithm. It will allow us to perform fast distributed search on huge biological data for calculating person's similarity.
A lot of recent publications in bioinformatics
emphasize SNPs (Single Nucleotide Polymorphism) which
describe one bit of difference in DNA between members of
a species [
Almost all common SNPs have only two variations
(alleles) so they can be described as only one binary bit
each. More than 6.2 million human SNPs are presented
now in public databases (e.g. in [
Based on SNPs of a group of people one can
construct a phylogenetic network [
Recently introduced the personal web service by [
Our idea is to provide framework to store and analyze a lot of SNPs for the large number of individuals. So everyone will be able to:
As long as number of individuals and number of SNPs can be huge (each more than 106), familiar methods do not work in acceptable time.
In this research we focus on clustering this binary
data to ensure fast search. We use a combination of
stochastic approximate methods of cluster optimization
with other combinatorial methods [
We construct phylogenetic networks for each cluster and then use it for understanding underlying biological dependencies. Different types of networks and different constraints on data give us wide tradeoff between complexity and accuracy.
We do not consider legal aspects (such as discrimination and human rights) because it is not a subject of this research. From the practice of existent social networks sharing personal data and searching among them are possible and do not conflict with a law. 2 2.1
Each person has a bit sequence where every bit represents one SNP (almost all common SNPs have only two alleles). Some SNPs (or group of them) can be additionally described (e.g. ”hair color”, ”eye color”, ”height” etc.) for convenient usage.
Mary Bill Ann
If we have N individuals and M different SNPs, these data form matrix D with N rows and M columns.
Besides SNPs such type of matrix can present a lot of other data, e.g. market baskets, graph connections etc. 2.2
"Find all individuals that are equal to the given one in the given SNP positions with the given error" It is reasonable to get a list of these individuals ordered by an error. More formal, query input consist of: individual number p : 1 p
N , set of SNP indices a = [a1; :::; aT ], 1 ai
M , integer error k
0.
The difference between two persons p and r on SNPs a can be defined as Hamming distance between corresponding bit subsequences: dif fa(p; r) = H(Dp;a; Dr;a) = Dr;ai );
For instance, the difference between Mary and Ann on SNPs (1; 3; 5; 6; 7) will be the following: T X (Dp;ai i=1 dif f[1;3;5;6;7]( 2 ; 4 ) = H(10101; 00111) = 2: 0 0
1 D = BB @ 0 0 Finally, query answer is an ordered by dif f list: A(p; a; k) = fr 2 [1::N ] : dif fa(p; r) kg :
A native implementation of this search will calculate dif fa(p; r) for every r. It works in O(N T ) time and is not acceptable for large N and T . Also, if T << M then we do not need to keep all N M matrix in memory and can request only small necessary parts of it. To address these issues we introduce matrix partitioning. 2.3
The main objective of this research is to divide a matrix D into a number of submatrices (C1; :::; Cs) in such a way to guarantee a fast execution of search query.
Each submatrix (let’s name it ”cluster”) Ci can be described with two vectors: indices of rows and indices of columns in the original matrix D. For instance: 0 0
1
D = BB
@ 0
0
We often use synonyms ”part”, ”cluster” or ”class” for
”submatrix”. And the process of dividing matrix into
parts can be named as ”partitioning”, ”clustering” or
even ”classification”. A ”person” sometimes can be an
”individual” or even just a ”biological entity”.
The problem of clustering is partitioning of a data space
X into some classes. It means that points in the same
class share some common trait and this trait forms this
class. Such property, for example, can be a closeness
of the point to some ”center”. Formally, the problem
is to find an assignment function: x 2 X ! c 2 C
where C is a set of clusters [
Also there are penalty functions which increase if x moves far from the center of a corresponding class.
Thus, clustering problem can be described as estimation such parameters that minimize an average risk functional or finding the class centers in which a total dispersion is minimal.
The adaptive optimization algorithm is characterized
by accumulating the information during the search of an
extremum and using it to increase probability of
convergence to an optimum [
Classically phylogenetic network is a directed acyclic graph containing one root node, a set of internal nodes and exact n leaves. Every node has associated bit sequence of equal lengths. Every internal node can have either one or two incoming edges. One edge biologically means ”single polymorphism” and can change single bit of sequence from 0 to 1 and each position changes only once in whole network. Two incoming edges mean ”single-crossover recombination” and form a new sequence as a composition of two ancestors, such a node calls recombination node. A phylogenetic network without recombination nodes turns out perfect phylogenetic tree.
A complete definition can be found in [
Also, there are different concepts of phylogenetic
networks and this provides a wide variety of data structures
and algorithms. In [
Network construction algorithms are also widely
described in literature and vary in supported types of the
network, complexity, proved bounds (e.g. of number of
recombinations) etc. [
The initial problem is proposed to be divided into several subproblems. 4.1
For this purpose we plan to use clustering by an
adaptive algorithm of random search [
In this case we have following key choices: 1. type of risk function for clusterization, 2. type of phylogenetic networks.
A risk function will also strongly depend on constraints of sequences to fit phylogenetic networks. Also still network constructing complexity can be more than O(nm) and we need high parallelism for fast search, we cannot allow huge clusters. 4.2
1. search of appropriate set of clusters, 2. local search inside of this set.
It has become complicated because partitioning makes parts (clusters) not only with different individuals (rows), but also with different SNPs too (columns). So the whole search query for one person can occur in more than one cluster and highly distributed search should be used.
As interesting achievement of this approach we can notice a secure query execution because of data distribution between a lot of clusters. So this system can form something like anonymous peer-to-peer network where nobody knows significant information about others, but still can execute search queries. 5
Binary matrix clustering is a widely studied field, but
most papers emphasize grouping only 1s by some rule,
considering binary matrix as a plain where 1 means the
point and 0 means the gap [
D = AXBT + E; where X is a centroid, A and B are somewhat smaller than D matrices and E is an error matrix.
Our claim is to use all initial data and partition whole matrix into clusters. We will try to absorb existed ideas and modify them for proposed problem.
Data clustering in general case is reviewed by Anil K.
Jain in [
In [
Phylogenetic networks based on bit sequences have
rapidly growing research, e.g. in [
Nowadays there are a lot of individual genome information available for each person, and this information processing will make a significant role in future.
We stated the problem of the binary matrix partitioning in a key of biological search and have a plan to investigate the usage of adaptive algorithms of random search for clustering binary data. Using the set of phylogenetic networks we want to support a fast search operation for personal similarity evaluation. There are a lot of different types of networks, so we need to choose appropriate one and analyze its search abilities and possibilities to divide the initial matrix in such a way to satisfy constraints on sequences. 7
In this research we focus more on clustering, while distributed search algorithm will be described shortly and only in significant parts. More details and optimization are remained for future. Also, we can try to support more complex queries than presented in this paper.
Measurement errors that are frequent in biology were not mentioned either. Security and anonymization of this system can also be investigated in future.