Biomine is a search engine prototype under development. It can be used to find biological entities that are (indirectly) related to given query entities, as well as to display and evaluate the relations. Biomine is based on an integrated index to a number of public biological databases. The representation is a probabilistic graph, where nodes correspond to biological entities (typically a record in a biological database) and edges to their relationships (typically a cross-reference between database records). Edges are annotated with probabilities that reflect the strength or the reliability of the relation. I will discuss research problems and challenges for search in such graphs.