Identifying Similar Non-Lattice Subgraphs in Gene Ontology based on Structural Isomorphism and Semantic Similarity of Concept Labels.

Non-Lattice Subgraphs (NLSs) are graph fragments of a terminology which violates the lattice property, a desirable property for a well-formed terminology. They have been proven to be useful in identifying inconsistencies in biomed-ical terminologies. Similar NLSs may denote similar inconsistencies that may suggest possibly similar remediations. Therefore, we investigate a structural-semantic-based approach to identify similar NLSs in the Gene Ontology (GO). For an input NLS, we first obtain all its isomorphic NLSs. Then, we compare each concept of the input NLS with the corresponding concept in an isomorphic NLS and then compute a similarity score for the two NLSs. Applying this approach to 10 different structures of NLSs in GO, we found that 38.43% (910/2368) of NLSs have at least one similar NLS. We also observed some interesting lexical patterns frequently existing in similar NLSs. Our approach may be applicable to other biomedical terminologies for identifying similar NLSs.