This paper studies new variants of the co-evolution model for prediction of protein-protein interactions from sequence information. Given two query proteins, the method uses information extracted from a database search to generate a multiple alignment and compute the likelihood that the two proteins interact. The model uses four elements, starting from the correlated divergence between proteins from different species, through potentials of correlated mutations, charge and hydrogen bonds. The significance of these measures is estimated from large populations of interacting and non interacting protein pairs. A variant over an EM algorithm is used to identify the subset of the database proteins (the homologs of the query proteins) that are more likely to interact, and a modified correlated mutations model is employed to maximize the strength of the signals. The algorithm not only tries to suggest if two proteins interact, but also attempts to detect the localized binding box interaction region, information that is hardly ever available. We tune and test our model over a large set of protein interactions we extract from BIND.