Hierarchical Directed Acyclic Graph (HDAG)
A Hierarchical Directed Acyclic Graph (HDAG) is a Directed Acyclic Graph with Hierarchical Structures.
- Context:
- It can have graph nodes that are also directed acyclic graphs.
- Example(s):
- Counter-Example(s):
- See: Graph Node, Graph Edge, Graph Drawing, Composite Node, Kernel Function, Digraph.
References
2017
- (Notaro et Al., 2017) ⇒ Marco Notaro, Max Schubach, Peter N. Robinson, and Giorgio Valentini (2017). “Prediction of Human Phenotype Ontology terms by means of Hierarchical Ensemble methods", BMC Bioinformatics, 18(1):449,doi:10.1186/s12859-017-1854-y
- ABSTRACT: Background. The prediction of human gene–abnormal phenotype associations is a fundamental step toward the discovery of novel genes associated with human disorders, especially when no genes are known to be associated with a specific disease. In this context the Human Phenotype Ontology (HPO) provides a standard categorization of the abnormalities associated with human diseases. While the problem of the prediction of gene–disease associations has been widely investigated, the related problem of gene–phenotypic feature (i.e., HPO term) associations has been largely overlooked, even if for most human genes no HPO term associations are known and despite the increasing application of the HPO to relevant medical problems. Moreover most of the methods proposed in literature are not able to capture the hierarchical relationships between HPO terms, thus resulting in inconsistent and relatively inaccurate predictions.
Results. We present two hierarchical ensemble methods that we formally prove to provide biologically consistent predictions according to the hierarchical structure of the HPO. The modular structure of the proposed methods, that consists in a “flat” learning first step and a hierarchical combination of the predictions in the second step, allows the predictions of virtually any flat learning method to be enhanced. The experimental results show that hierarchical ensemble methods are able to predict novel associations between genes and abnormal phenotypes with results that are competitive with state-of-the-art algorithms and with a significant reduction of the computational complexity.
Conclusions. Hierarchical ensembles are efficient computational methods that guarantee biologically meaningful predictions that obey the true path rule, and can be used as a tool to improve and make consistent the HPO terms predictions starting from virtually any flat learning method. The implementation of the proposed methods is available as an R package from the CRAN repository.
- ABSTRACT: Background. The prediction of human gene–abnormal phenotype associations is a fundamental step toward the discovery of novel genes associated with human disorders, especially when no genes are known to be associated with a specific disease. In this context the Human Phenotype Ontology (HPO) provides a standard categorization of the abnormalities associated with human diseases. While the problem of the prediction of gene–disease associations has been widely investigated, the related problem of gene–phenotypic feature (i.e., HPO term) associations has been largely overlooked, even if for most human genes no HPO term associations are known and despite the increasing application of the HPO to relevant medical problems. Moreover most of the methods proposed in literature are not able to capture the hierarchical relationships between HPO terms, thus resulting in inconsistent and relatively inaccurate predictions.
2014
- (Alefragis et al., 2014) ⇒ Alefragis, P., Gogos, C., Valouxis, C., Goulas, G., Voros, N., & Housos, E. (2014). "Assigning and Scheduling Hierarchical Task Graphs to Heterogeneous Resources" (PDF). 10th International Conference of the Practice and Theory of Automated Timetabling.
- ABSTRACT: Task Scheduling is an important problem having many practical applications. More often than not, precedence constraints exist between tasks, and a common way to capture them is through Directed Acyclic Graphs (DAGs). A DAG might contain a great number of tasks representing complex real life scenarios. It might be the case that logical groupings of tasks exist giving a hierarchical nature to the graph. Such Hierarchical Task Graphs (HTGs) have nodes that are further analyzed to DAGs or to other HTGs. In this paper a method of solving an HTG problem is presented based on the idea of gradually solving the problem by replacing subgraphs with virtual nodes. Integer Programming is used to generate virtual nodes that replace a subgraph, results from solving the subgraph problem using. So a series of subproblems are solved and starting from the deeper levels of the HTG a solution to the full problem emerges.
2006
- (PARC Glossary, 2006) ⇒ (2006). "HDAG" In: Glossary of Sensemaking Terms http://www2.parc.com/istl/groups/hdi/sensemaking/glossary.htm
- HDAG - Hierarchical directed acyclic graph. A graph structure with nodes and links. In an HDAG, a node can itself contain a subgraph. A link into a composite node in an HDAG is equivalent to a link to every root node in the contained subgraph. A link out of a composite node in an HDAG is equivalent to a link out of every fringe node in the contained subgraph.
2003
- (Suzuki et al., 2003) ⇒ Suzuki, J., Hirao, T., Sasaki, Y., & Maeda, E. (2003, July). "Hierarchical directed acyclic graph kernel: Methods for structured natural language data" (PDF). In: Proceedings of the 41st Annual Meeting on Association for Computational Linguistics-Volume 1 (pp. 32-39). Association for Computational Linguistics. DOI: 10.3115/1075096.1075101
- ABSTRACT: This paper proposes the “Hierarchical Directed Acyclic Graph (HDAG) Kernel” for structured natural language data. The HDAG Kernel directly accepts several levels of both chunks and their relations, and then efficiently computes the weighed sum of the number of common attribute sequences of the HDAGs. We applied the proposed method to question classification and sentence alignment tasks to evaluate its performance as a similarity measure and a kernel function. The results of the experiments demonstrate that the HDAG Kernel is superior to other kernel functions and baseline methods.