perl module for context grammar?

[ela]

While there is another perl module that deals with the following complex
structure,

(((((((R1441:65.00000000,X29:44.66666667):42.33333333,(R1842:3.00000000,R1909:9.00000000):1.33333333):1.33333333,(R1390:13.00000000,R1505:8.00000000):2.33333333):4.00000000,X122:4.66666667):25.33333333,((CCDC5180:23.00000000,HN878:22.00000000):10.00000000,(CCDC5079:28.00000000,(BT1:28.00000000,BT2:36.00000000):1.00000000):20.00000000):0.00000000):1.00000000,BS1:12.00000000):45.00000000,(R1207:9.00000000,(R1746:40.00000000,((X132:0.00000000,X28:0.00000000):6.50000000,(X156:67.83333333,X85:51.83333333):52.33333333):3.50000000):4.00000000):62.00000000,(kzn4207:6.00000000,(kznR506:3.00000000,kznV2475:2.00000000):8.00000000):245.00000000);

the module does not have the function I need. Is there any standard perl
module that can allocate the nodes in a hierarchical tree structure (e.g.
R1441 and X29 are in the same sub-group, and then this sub-group is under
the same super-group with the subgroup formed by R1842-R1909);
after forming this hierarchical structure, distances between any nodes can
be easily derived (e.g. the distance of R1441 and X29 is 65+44.67, R1441 and
R1842 is (65+42.3) + (3+1.3), you can see that if the subgroups are further
apart, they have to trace more upper level to derive the pairwise distance).
Another derivation is about intermediate nodes. For example, the distance
between subgroup R1441-X29 and end node R1909 is 42.3+ (9+1.3)

 

[Jim Gibson]

While there is another perl module that deals with the following complex
structure,


(((((((R1441:65.00000000,X29:44.66666667):42.33333333,(R1842:3.00000000,R1909:
9.00000000):1.33333333):1.33333333,(R1390:13.00000000,R1505:8.00000000):2.3333
3333):4.00000000,X122:4.66666667):25.33333333,((CCDC5180:23.00000000,HN878:22.
00000000):10.00000000,(CCDC5079:28.00000000,(BT1:28.00000000,BT2:36.00000000):
1.00000000):20.00000000):0.00000000):1.00000000,BS1:12.00000000):45.00000000,(
R1207:9.00000000,(R1746:40.00000000,((X132:0.00000000,X28:0.00000000):6.500000
00,(X156:67.83333333,X85:51.83333333):52.33333333):3.50000000):4.00000000):62.
00000000,(kzn4207:6.00000000,(kznR506:3.00000000,kznV2475:2.00000000):8.000000
00):245.00000000);

the module does not have the function I need. Is there any standard perl
module that can allocate the nodes in a hierarchical tree structure (e.g.
R1441 and X29 are in the same sub-group, and then this sub-group is under
the same super-group with the subgroup formed by R1842-R1909);
after forming this hierarchical structure, distances between any nodes can
be easily derived (e.g. the distance of R1441 and X29 is 65+44.67, R1441 and
R1842 is (65+42.3) + (3+1.3), you can see that if the subgroups are further
apart, they have to trace more upper level to derive the pairwise distance).
Another derivation is about intermediate nodes. For example, the distance
between subgroup R1441-X29 and end node R1909 is 42.3+ (9+1.3)

I would recommend the book "Pro Perl Parsing", by Christopher M. Frenz,
Apress, and the module Parse::RecDescent (but the latter has a steep
learning curve).

 

[Keith Keller]

While there is another perl module that deals with the following complex
structure,

(((((((R1441:65.00000000,X29:44.66666667):42.33333333,(R1842:3.00000000,R1909:9.00000000):1.33333333):1.33333333,(R1390:13.00000000,R1505:8.00000000):2.33333333):4.00000000,X122:4.66666667):25.33333333,((CCDC5180:23.00000000,HN878:22.00000000):10.00000000,(CCDC5079:28.00000000,(BT1:28.00000000,BT2:36.00000000):1.00000000):20.00000000):0.00000000):1.00000000,BS1:12.00000000):45.00000000,(R1207:9.00000000,(R1746:40.00000000,((X132:0.00000000,X28:0.00000000):6.50000000,(X156:67.83333333,X85:51.83333333):52.33333333):3.50000000):4.00000000):62.00000000,(kzn4207:6.00000000,(kznR506:3.00000000,kznV2475:2.00000000):8.00000000):245.00000000);

the module does not have the function I need.

You don't mention what module you're using. If that's a Newick format,
have you looked at the Bioperl Bio::Tree modules?

--keith

 

[ela]

You don't mention what module you're using. If that's a Newick format,
have you looked at the Bioperl Bio::Tree modules?

While this module contains functions like "get_lca" to check supergroup,
there is no further documentation how the distance from this supergroup with
other nodes can be obtained. Moreover, the data structure is encapsulated
and so while there is another function called "is_monophyletic", I cannot
actually trace back hierarchically from the leaf to get more "nearest
neighbor" nodes but have to exhaust all the nodes and derive the relation
(or hierarchy) myself. That's why I posted a question here to see if
standard Perl modules have dealt with this.

 

[ela]

I would recommend the book "Pro Perl Parsing", by Christopher M. Frenz,
Apress, and the module Parse::RecDescent (but the latter has a steep
learning curve).

Oh, it's CHAPTER 5 Performing Recursive-Descent Parsing with
Parse::RecDescent . . . I guess the module actually uses this. Let me read
that first and thanks for telling me this kind of problem is called
"recursive decent parsing"!

 

[sln]

While there is another perl module that deals with the following complex
structure,

(((((((R1441:65.00000000,X29:44.66666667):42.33333333,(R1842:3 ...

Formatting the structure goes a long way.
(

(

(

(

(

(

(
R1441 : 65.00000000 ,
X29 : 44.66666667

) : 42.33333333 ,

(
R1842 : 3.00000000 ,
R1909 : 9.00000000

) : 1.33333333

) : 1.33333333 ,

(
R1390 : 13.00000000 ,
R1505 : 8.00000000

) : 2.33333333

) : 4.00000000 ,
X122 : 4.66666667

) : 25.33333333 ,

(

(
CCDC5180 : 23.00000000 ,
HN878 : 22.00000000

) : 10.00000000 ,

(
CCDC5079 : 28.00000000 ,

(
BT1 : 28.00000000 ,
BT2 : 36.00000000

) : 1.00000000

) : 20.00000000

) : 0.00000000

) : 1.00000000 ,
BS1 : 12.00000000

) : 45.00000000 ,

(
R1207 : 9.00000000 ,

(
R1746 : 40.00000000 ,

(

(
X132 : 0.00000000 ,
X28 : 0.00000000

) : 6.50000000 ,

(
X156 : 67.83333333 ,
X85 : 51.83333333

) : 52.33333333

) : 3.50000000

) : 4.00000000

) : 62.00000000 ,

(
kzn4207 : 6.00000000 ,

(
kznR506 : 3.00000000 ,
kznV2475 : 2.00000000

) : 8.00000000

) : 245.00000000

)

 

[Ted Zlatanov]

e> Oh, it's CHAPTER 5 Performing Recursive-Descent Parsing with
e> Parse::RecDescent . . . I guess the module actually uses this. Let me read
e> that first and thanks for telling me this kind of problem is called
e> "recursive decent parsing"!

No, the problem is how to parse, the solution (algorithm) is recursive
descent (not "decent" although it is decent for most problems

There are actually many types and subtypes of parsers with many, many
applications. The one you're describing is fairly simple, but if
Bioperl has a parser for it already, just look inside the module and see
if you can augment it with the functions you need. It sounds like this
distance is a pretty basic function, so you should be able to either
write it yourself or ask the module maintainers for help.

Ted

 

[ela]

No, the problem is how to parse, the solution (algorithm) is recursive
descent (not "decent" although it is decent for most problems

Thanks for correcting the typo.

There are actually many types and subtypes of parsers with many, many
applications. The one you're describing is fairly simple, but if
Bioperl has a parser for it already, just look inside the module and see
if you can augment it with the functions you need. It sounds like this
distance is a pretty basic function, so you should be able to either
write it yourself or ask the module maintainers for help.

Oh, I haven't thought about asking the original module maintainers for
advice. Thanks a lot!

 

[Ted Zlatanov]

e> Thanks for correcting the typo.

Sure, the "descent" part is actually pretty interesting if you're ever
curious about parsing. I recommend "Parsing Techniques: A Practical
Guide" by Grune and Jacobs; at least the first few chapters are easy to
understand and introduce parsing well. It's free on the authors' web site.

Ted