Background: Uncharacterized proteins from newly sequenced genomes prov
ide perfect targets for fold and function prediction. Results: For 38%
of the entire genome of Mycoplasma genitalium, sequence similarity to
a protein with a known structure can be recognized using a new sequen
ce alignment algorithm. When comparing genomes of IM. genitalium and E
scherichia coli, > 80% of M. genitalium proteins have a significant se
quence similarity to a protein in E. coli and there are > 40 examples
that have not been recognized before. For all cases of proteins with s
ignificant profile similarities, there are strong analogies in their f
unctions, if the functions of both proteins are known. The results pre
sented here and other recent results strongly support the argument tha
t such proteins are actually homologous. Assuming this homology allows
one to make tentative functional assignments for > 50 previously unch
aracterized proteins, including such intriguing cases as the putative
beta-lactam antibiotic resistance protein in M. genitalium. Conclusion
s: Using a new profile-to-profile alignment algorithm, the three-dimen
sional fold can be predicted for almost 40% of proteins from a genome
of the small bacterium M. genitalium, and tentative function can be as
signed to almost 80% of the entire genome. Some predictions lead to ne
w insights about known functions or point to hitherto unexpected featu
res of M. genitalium.