A Grammatical Approach to the Alignment of Structure-Annotated Strings

Shinnosuke SEKI; Satoshi KOBAYASHI

doi:10.1093/ietisy/e88-d.12.2727

A Grammatical Approach to the Alignment of Structure-Annotated Strings

Shinnosuke SEKI, Satoshi KOBAYASHI

Full Text Views

0

Cite this

Summary :

In this paper, we are concerned with a structural ambiguity problem of tree adjoining grammars (TAGs), which is an essential problem when we try to model consensus structures of given set of ribonucleic acid (RNA) secondary structures by TAGs. RNA secondary structures can be represented as strings with structural information, and TAGs have a descriptive capability of this kind of strings, what we call structure-annotated strings. Thus, we can model RNA secondary structures by TAGs. It is sufficient to use existing alignment methods for just computing the optimal alignment between RNA secondary structures. However, when we also want to model the resulting alignment by grammars, if we adopt these existing methods, then we may fail in modeling the alignment result by grammars. Therefore, it is important to introduce a new alignment method whose alignment results can be appropriately modeled by grammars. In this paper, we will propose an alignment method based on TAG's derivations each corresponding to a given RNA secondary structure. For an RNA secondary structure, there exist a number of derivations of TAGs which correspond to the structure. From the grammatical point of view, the property of TAGs drives us to the question how we should choose a derivation from these candidates in order to obtain an optimal alignment. This is the structural ambiguity problem of TAGs, which will be mainly discussed in this paper. For dealing with this problem appropriately, we will propose an edit distance between two structure-annotated strings, and then present an algorithm which computes an optimal alignment based on the edit distance.

Publication: IEICE TRANSACTIONS on Information Vol.E88-D No.12 pp.2727-2737

Publication Date: 2005/12/01

Publicized

Online ISSN

DOI: 10.1093/ietisy/e88-d.12.2727

Type of Manuscript: PAPER

Category: Automata and Formal Language Theory

Cite this

Copy

Shinnosuke SEKI, Satoshi KOBAYASHI, "A Grammatical Approach to the Alignment of Structure-Annotated Strings" in IEICE TRANSACTIONS on Information, vol. E88-D, no. 12, pp. 2727-2737, December 2005, doi: 10.1093/ietisy/e88-d.12.2727.
Abstract: In this paper, we are concerned with a structural ambiguity problem of tree adjoining grammars (TAGs), which is an essential problem when we try to model consensus structures of given set of ribonucleic acid (RNA) secondary structures by TAGs. RNA secondary structures can be represented as strings with structural information, and TAGs have a descriptive capability of this kind of strings, what we call structure-annotated strings. Thus, we can model RNA secondary structures by TAGs. It is sufficient to use existing alignment methods for just computing the optimal alignment between RNA secondary structures. However, when we also want to model the resulting alignment by grammars, if we adopt these existing methods, then we may fail in modeling the alignment result by grammars. Therefore, it is important to introduce a new alignment method whose alignment results can be appropriately modeled by grammars. In this paper, we will propose an alignment method based on TAG's derivations each corresponding to a given RNA secondary structure. For an RNA secondary structure, there exist a number of derivations of TAGs which correspond to the structure. From the grammatical point of view, the property of TAGs drives us to the question how we should choose a derivation from these candidates in order to obtain an optimal alignment. This is the structural ambiguity problem of TAGs, which will be mainly discussed in this paper. For dealing with this problem appropriately, we will propose an edit distance between two structure-annotated strings, and then present an algorithm which computes an optimal alignment based on the edit distance.
URL: https://global.ieice.org/en_transactions/information/10.1093/ietisy/e88-d.12.2727/_p

Copy

@ARTICLE{e88-d_12_2727,
author={Shinnosuke SEKI, Satoshi KOBAYASHI, },
journal={IEICE TRANSACTIONS on Information},
title={A Grammatical Approach to the Alignment of Structure-Annotated Strings},
year={2005},
volume={E88-D},
number={12},
pages={2727-2737},
abstract={In this paper, we are concerned with a structural ambiguity problem of tree adjoining grammars (TAGs), which is an essential problem when we try to model consensus structures of given set of ribonucleic acid (RNA) secondary structures by TAGs. RNA secondary structures can be represented as strings with structural information, and TAGs have a descriptive capability of this kind of strings, what we call structure-annotated strings. Thus, we can model RNA secondary structures by TAGs. It is sufficient to use existing alignment methods for just computing the optimal alignment between RNA secondary structures. However, when we also want to model the resulting alignment by grammars, if we adopt these existing methods, then we may fail in modeling the alignment result by grammars. Therefore, it is important to introduce a new alignment method whose alignment results can be appropriately modeled by grammars. In this paper, we will propose an alignment method based on TAG's derivations each corresponding to a given RNA secondary structure. For an RNA secondary structure, there exist a number of derivations of TAGs which correspond to the structure. From the grammatical point of view, the property of TAGs drives us to the question how we should choose a derivation from these candidates in order to obtain an optimal alignment. This is the structural ambiguity problem of TAGs, which will be mainly discussed in this paper. For dealing with this problem appropriately, we will propose an edit distance between two structure-annotated strings, and then present an algorithm which computes an optimal alignment based on the edit distance.},
keywords={},
doi={10.1093/ietisy/e88-d.12.2727},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - A Grammatical Approach to the Alignment of Structure-Annotated Strings
T2 - IEICE TRANSACTIONS on Information
SP - 2727
EP - 2737
AU - Shinnosuke SEKI
AU - Satoshi KOBAYASHI
PY - 2005
DO - 10.1093/ietisy/e88-d.12.2727
JO - IEICE TRANSACTIONS on Information
SN -
VL - E88-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 2005
AB - In this paper, we are concerned with a structural ambiguity problem of tree adjoining grammars (TAGs), which is an essential problem when we try to model consensus structures of given set of ribonucleic acid (RNA) secondary structures by TAGs. RNA secondary structures can be represented as strings with structural information, and TAGs have a descriptive capability of this kind of strings, what we call structure-annotated strings. Thus, we can model RNA secondary structures by TAGs. It is sufficient to use existing alignment methods for just computing the optimal alignment between RNA secondary structures. However, when we also want to model the resulting alignment by grammars, if we adopt these existing methods, then we may fail in modeling the alignment result by grammars. Therefore, it is important to introduce a new alignment method whose alignment results can be appropriately modeled by grammars. In this paper, we will propose an alignment method based on TAG's derivations each corresponding to a given RNA secondary structure. For an RNA secondary structure, there exist a number of derivations of TAGs which correspond to the structure. From the grammatical point of view, the property of TAGs drives us to the question how we should choose a derivation from these candidates in order to obtain an optimal alignment. This is the structural ambiguity problem of TAGs, which will be mainly discussed in this paper. For dealing with this problem appropriately, we will propose an edit distance between two structure-annotated strings, and then present an algorithm which computes an optimal alignment based on the edit distance.
ER -