On Correlation Detection and Alignment Recovery of Gaussian Databases

Two fundamental problems in the statistical analysis of Gaussian databases are correlation detection (or testing) and alignment recovery. Correlation detection of two databases is basically a hypothesis testing problem; under the null hypothesis, the databases are independent, and under the alternate hypothesis, there exists a permutation, for which the databases are correlated. In this task, the main objective is to attain the best trade-off between the type-I and type-II error probabilities. In the problem of database alignment recovery, we make an assumption that the two databases are correlated, and want to estimate the underlying permutation. The objective is to minimize the probability of alignment error. While alignment recovery of databases with n sequences, each containing d Gaussian entries has been recently studied in [1] and correlation detection of such Gaussian databases has been lately explored in [2], it seems very natural to tackle the two individual problems together as a joint problem of correlation detection and alignment recovery. In addition, we also refer to the problem of partial alignment recovery, in which one would like to estimate only part of the underlying alignment between the databases. The main reasons for preferring partial alignment recovery instead of full alignment recovery are as follows.