An approach is described for genomic database searching based on experimentally observed proteolytic fragments, e.g., isolated from 1D or 2D gels or analyzed directly, that can be applied to unfinished prokaryotic genomic data in the absence of annotations or previously assigned open reading frames (ORFs). This variation on the database search is in contrast to the more familiar use of peptide mass spectral fragmentation data to search fully annotated inferred protein databases, e.g., OWL or SWISS-PROT. We compared the SEQUEST search results from a six reading frame translation of the Porphyromonas gingivalis genome DNA sequence with those from computationally derived ORFs created using publicly available genomics software tools. The ORF approach eliminated many of the artifacts present in output from the six reading frame search. The method was applied to uninterpreted tandem mass spectrometric data derived from proteins secreted by the periodontal pathogen Porphyromonas gingivalis in response to the gingival epithelial cell environment, a model system for the study of host-pathogen interactions relevant to human periodontal disease.