Cork oak decline in Mediterranean forests is a complex phenomenon, observed with remarkable frequency in the southern part of the Iberian Peninsula, causing the weakening and death of these woody plants. The defoliation of the canopy, the presence of dry peripheral branches, and exudations on the trunk are visible symptoms used for the prognosis of decline, complemented by the presence of Phytophthora cinnamomi identified in the rhizosphere of the trees and adjacent soils. Recently, a large proteomic dataset obtained from the leaves of cork oak plants inoculated and non-inoculated with P. cinnamomi has become available. We explored it to search for an optimal set of proteins, markers of the biological pattern of interaction with the oomycete. Thus, using published data from the cork oak leaf proteome, we mathematically modelled the problem as an α, β-k-Feature Set Problem to select molecular markers. A set of proteins (features) that represent dominant effects on the host metabolism resulting from pathogen action on roots was found. These results contribute to an early diagnosis of biochemical changes occurring in cork oak associated with P. cinnamomi infection. We hypothesize that these markers may be decisive in identifying trees that go into decline due to interactions with the pathogen, assisting the management of cork oak forest ecosystems.