Integer programming-based method for grammar-based tree compression and its application to pattern extraction of glycan tree structures

Table 2 Statistics of glycans, G02703, G03655, G03710, G04045, G04458, G04666, G04859, G05058,G05256, G05552, G06867, and G09054, and results on the grammar size

glycan	max degree	# vertices	# distinct labels	Min SEOTG		Min SEUTG		TREE-BISECTION
glycan	max degree	# vertices	# distinct labels	size	time	size	time	size	time
G02703	3	26	3	22	3.68	22	2.9	32	0.001
G03655	3	34	3	47	0.96	47	2.32	49	0.001
G03710	3	28	3	20	0.47	20	0.51	20	0.001
G04045	3	36	3	20	1.77	20	1.98	22	0.001
G04458	3	21	2	16	1.55	16	0.69	36	0.001
G04666	3	20	4	25	1.41	25	0.94	33	0.001
G04859	3	19	5	27	0.12	27	0.25	29	0.001
G05058	3	25	5	26	3.03	26	66.28	36	0.001
G05256	3	25	2	19	3.14	19	3.98	29	0.001
G05552	3	19	5	27	0.66	23	0.23	27	0.001
G06867	3	28	3	22	2.22	22	6.46	26	0.001
G09054	4	31	5	29	2.81	29	6.71	29	0.001

Statistics of glycans, G02703, G03655, G03710, G04045, G04458, G04666, G04859, G05058, G05256, G05552, G06867, and G09054, and results on the grammar size and the elapsed time (seconds) by our proposed IP-based methods for the minimum SEOTG and SEUTG problems, and TREE-BISECTION [10].

ISSN: 1471-2105