TY - JOUR
T1 - Ligand-Receptor Pairing Via Tree Comparison
JF - Journal of Computational Biology
Y1 - 2000
A1 - Bafna,Vineet
A1 - Hannenhalli, Sridhar
A1 - Rice,Ken
A1 - Vawter,Lisa
AB - This paper introduces a novel class of tree comparison problems strongly motivated by an important and cost intensive step in drug discovery pipeline viz., mapping cell bound receptors to the ligands they bind to and vice versa. Tree comparison studies motivated by problems such as virus-host tree comparison, gene-species tree comparison and consensus tree problem have been reported. None of these studies are applicable in our context because in all these problems, there is a well-defined mapping of the nodes the trees are built on across the set of trees being compared. A new class of tree comparison problems arises in cases where finding the correspondence among the nodes of the trees being compared is itself the problem. The problem arises while trying to find the interclass correspondence between the members of a pair of coevolving classes, e.g., cell bound receptors and their ligands. Given the evolution of the two classes, the combinatorial problem is to find a mapping among the leaves of the two trees that optimizes a given cost function. In this work we formulate various combinatorial optimization problems motivated by the aforementioned biological problem for the first time. We present hardness results, give an efficient algorithm for a restriction of the problem and demonstrate its applicability.
VL - 7
SN - 1066-5277, 1557-8666
UR - http://www.liebertonline.com/doi/abs/10.1089/10665270050081388
CP - 1-2
M3 - 10.1089/10665270050081388
ER -