A family of metrics for biopolymers based on counting independent sets

作者：Rocha J^*; Llabres M; Alberich R

来源：Computational Biology and Chemistry, 2005, 29(5): 337-344.

DOI：10.1016/j.compbiolchem.2005.08.003

• counting-independent sets
• graph distance
• edge ideal metric
• Hilbert polynomial
• cliques

We introduce a new family of metrics for graphs of fixed size, based on counting-independent sets. Our definition is simpler and easier to calculate than the edge ideal metric family defined by Llabres and Rossello without loosing any of its abstract properties. We contrast them on some examples with graphs that represent protein secondary and three-dimensional (3D) structures. We conclude that although the edge ideal metrics are faster to calculate on some sparse graphs, in general, the independent set metrics are more tractable.

• 出版日期2005-10