University of Glasgow

Roderic Page

In an [earlier
post](http://iphylo.blogspot.com/2007/05/tbmap-paper-out.html) I
described the [TBMap](http://linnaeus.zoology.gla.ac.uk/~rpage/tbmap)
database
([doi:10.1186/1471-2105-8-158](http://dx.doi.org/10.1186/1471-2105-8-158)),
which contains a mapping of TreeBASE taxon names onto names in other
databases. While this is one step towards making it easier to query
TreeBASE, what I\'d really like is to link the data in TreeBASE to
sources such as GenBank and specimen databases. Part of the challenge of
doing this (and also doing it more generally, such as taking a NEXUS
file from the web and using that) is that the names people use in a
NEXUS data file are often not the actual taxonomic names. So, if I take
a table from a paper that lists GenBank accession numbers, voucher
specimens, etc., I\'m left with the problem of matching two sets of
names \-- those in the data file to those in the table.  
  
For example, this is a TreeBASE taxon **Apomys_sp.\_B_145699**. Using a
script I grabbed the sequences in this study and constructed a table
listing the name and specimen voucher for each sequence. The name
corresponding to the TreeBASE taxon is **Apomys \"sibuyan b\" FMNH
145699**. Clearly a similar string, but not the same.  
  
The approach I\'ve taken is to compare strings using the [longest common
subsequence](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem)
algorithm. Below are the two strings, with their longest common
subsequence highlighted in
[green]{style="background:rgb(100,255,100);color:black;"}.  
[  
[  
Apomys]{style="background:rgb(100,255,100);color:black;"}\_[s]{style="background:rgb(100,255,100);color:black;"}p.\_B\_[145699]{style="background:rgb(100,255,100);color:black;"}]{style="background:yellow;color:black;"}  
[  
[Apomys]{style="background:rgb(100,255,100);color:black;"}
\"[s]{style="background:rgb(100,255,100);color:black;"}ibuyan b\" FMNH
[145699]{style="background:rgb(100,255,100);color:black;"}  
]{style="background:yellow;color:black;"}  
The length of this subsequence is used to compute a measure of distance
between the two strings. If *len1* is the length of the first string,
*len2* is the length of the second string, and *lcs* is the length of
the longest common subsequence, then  
  
*d* = (*len1* + *len2*) - 2 × *lcs*  
  
We can normalise this by dividing by *len1* + *len2*, so that *d* ranges
from 0 (identical) to 1.0 (no similarity).  
  
So, now we have a measure of how similar the strings are, I still need
to find the set of matchings between file and table names. This can be
modelled an example of a [maximum weight bipartite matching
problem](http://en.wikipedia.org/wiki/Matching). Given a bipartite
graph, we want to find the matching with the highest weight. A
\"matching\" is where each node is connected to just one other node. For
example, given this graph:  
[![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9gVkeuINA2wOnQ9r_FdGa_2Da29F_18x6ywZEYjNIdd7uI_BMic4t0iAjdDv7ENykC_VvKAbreowCM8Y_6QLpVS7ySVEJPzuJF_1md2UJdYKel6FSxUGBDmB8epuuFQ6u619i/s320/bipartite.jpg){#BLOGGER_PHOTO_ID_5108885049432642946
style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;"
border="0"}](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEj9gVkeuINA2wOnQ9r_FdGa_2Da29F_18x6ywZEYjNIdd7uI_BMic4t0iAjdDv7ENykC_VvKAbreowCM8Y_6QLpVS7ySVEJPzuJF_1md2UJdYKel6FSxUGBDmB8epuuFQ6u619i/s1600-h/bipartite.jpg){onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"}  
  
a maximum weight matching is:  
  
[![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjuYbISQGTbzFxr6axJ0WHsfETfD7eZjISu-hW8SCdrP3hcY9ImRLQUeHdTUyZLF7ZB4OPho-1l7qoT2vCpwd1NK1wPcvhmi7rFv5LjUpHygRwQnwW4bc8ZiiwG0H5sgZO3ytaC/s320/matched.jpg){#BLOGGER_PHOTO_ID_5108885453159568786
style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;"
border="0"}](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjuYbISQGTbzFxr6axJ0WHsfETfD7eZjISu-hW8SCdrP3hcY9ImRLQUeHdTUyZLF7ZB4OPho-1l7qoT2vCpwd1NK1wPcvhmi7rFv5LjUpHygRwQnwW4bc8ZiiwG0H5sgZO3ytaC/s1600-h/matched.jpg){onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}"}  
  
In this example, four pairs of nodes are matched, one is \"orphaned\".
Applying this to the data matching problem, I take a list of names form
the NEXUS file, and a list of names from the paper (or supplementary
data file, etc.) and compute a maximum weight matching. Because I\'m
looking for the **maximum** weighted matching I actually want similarity
of names, hence I subtract the normalised *d* from 1.0.  
  
So, the algorithm consists of taking the two lists of names (taxa from
dataset and names from a table), computing the distance between all
pairs of names, then obtain the maximum weight bipartite matching.
Because for large sets of names the *n* × *m* the bipartite graph
becomes huge, and because in practice most matches are poor, for each
node in the graph I only draw the edges corresponding to the five most
similar pairs of strings.


In an earlier post I described the TBMap database (doi:10.1186/1471-2105-8-158), which contains a mapping of TreeBASE taxon names onto names in other databases. While this is one step towards making it easier to query TreeBASE, what I'd really like is to link the data in TreeBASE to sources such as GenBank and specimen databases.

Messaggi di Rogue Scholar

Matching names in phylogeny data files