I would suggest instead first looking for professors whose groups do data mining with medical or biological research, then worrying about what the degree will say. There are two types groups which you should look for, and which could both lead to a satisfactory experience.
The first type of group is one which focuses on answering biological or medical questions, and sometimes applies data mining techniques in an effort to answer those questions. This is how Prof. T.M. Murali's group (my current one) is built.
The second type of group works the other way around, focusing on data mining algorithms, and sometimes applying their techniques to biological and medical data. Prof. Naren Ramakrishnan's group is a good example of this.
Students graduate from both groups with a mix of degrees, some with "Bioinformatics" in the title, others with "Computer Science". In the end, it doesn't really matter much[*]; the group that you train with will mean more about what sort of education you got than which department issued your degree. Sometimes which department you enter simply comes down to funding issues. For example, maybe the Computer Science department can't support any more incoming students but the bioinformatics program is flush with cash. In these cases, an advisor may ask you to apply to her or his group via the bioinformatics program so that financial support won't be an issue.
I suggest researching for groups that do work that looks interesting to you, then contacting those professors describing your research interests and what you might like to do in their group, or applying to the programs directly. I would also suggest applying to programs where you can identify more than one professor with whom you might like to do research. Sometimes things will not work out: you may not get along with the advisor or the group, your advisor may lose funding or move, or you may find you don't actually like your research topic. Having other professors in the same university whose research interests you can save your chances of getting a degree.
[*] An exception I can think of is that you may encounter some trouble applying for industry jobs specifically seeking "Data Mining" in the degree (e.g., to a social networking or defense company) and your degree says "Bioinformatics" or "Medical Informatics". In these cases you will have to explain that your degree centered around data mining. In applying for a bioinformatics or medical informatics position, either degree would be happily recognized.