Secure outsourcing of DNA sequences comparisons in a Grid environment
Rachel Akimana, Olivier Markowitch, Yves Roggeman · 2007
Abstract: Computing and data Grids are widely distributed computing systems usually used to resolve scientific or technical problems that require a large amount of computing power and/or storage resources. To be really attractive, Grids must provide secured environments (in terms of confidentiality, data integrity, entity identification, etc). In this paper, we consider the confidentiality aspects of Grid’s applications related to string matching. We take as an example the area of genetic biology and, more precisely, the search of DNA similarities. Since DNA sequences comparisons need greedy and sensitive computations, we propose a model allowing to search DNA similarities in a public DNA database on the Grid. The model is related to private approximate string matching problem where neither the inputs nor the outputs of the comparisons are revealed. We analyze the performance of our proposed DNA disguising method by taking into account how the edit distances between the client’s queries and their corresponding disguises are distributed along the DNA sequences. In order to outweigh the client’s load of the initial proposed model, we propose also an extension of our model where the client’s load is executed by a third untrusted server. Key-Words: Grid systems, Secure outsourcing, Secure approximate matching 1