  Given the amino acid sequence of a protein, researchers often infer its
structure and function by finding homologous, or evolutionarily-related,
proteins of known structure and function. Since structure is typically more
conserved than sequence over long evolutionary distances, recognizing remote
protein homologs from their sequence poses a challenge.
  We first consider all proteins of known three-dimensional structure, and
explore how they cluster according to different levels of homology. An
automatic computational method reasonably approximates a human-curated
hierarchical organization of proteins according to their degree of homology.
  Next, we return to homology prediction, based only on the one-dimensional
amino acid sequence of a protein. Menke, Berger, and Cowen proposed a Markov
random field model to predict remote homology for beta-structural proteins, but
their formulation was computationally intractable on many beta-strand
topologies.
  We show two different approaches to approximate this random field, both of
which make it computationally tractable, for the first time, on all protein
folds. One method simplifies the random field itself, while the other retains
the full random field, but approximates the solution through stochastic search.
Both methods achieve improvements over the state of the art in remote homology
detection for beta-structural protein folds.
