A similarity measure for graphs with low computational complexity

We present and analyze an algorithm to measure the structural similarity of generalized trees, a new graph class which includes rooted trees. For this, we represent structural properties of graphs as strings and define the similarity of two Graphs as optimal alignments of the corresponding property stings. We prove that the obtained graph similarity measures are so called Backward similarity measures. From this we find that the time complexity of our algorithm is polynomial and, hence, significantly better than the time complexity of classical graph similarity methods based on isomorphic relations. (c) 2006 Elsevier Inc. All rights reserved.

Information theoretic measures of UHG graphs with low computational complexity

We introduce a novel graph class we call universal hierarchical graphs (UHG) whose topology can be found numerously in problems representing, e.g., temporal, spacial or general process structures of systems. For this graph class we show, that we can naturally assign two probability distributions, for nodes and for edges, which lead us directly to the definition of the entropy and joint entropy and, hence, mutual information establishing an information theory for this graph class. Furthermore, we provide some results under which conditions these constraint probability distributions maximize the corresponding entropy. Also, we demonstrate that these entropic measures can be computed efficiently which is a prerequisite for every large scale practical application and show some numerical examples. (c) 2007 Elsevier Inc. All rights reserved.

Family communication, genetic testing and colonoscopy screening in hereditary non-polyposis colon cancer: a qualitative study

Objective: Genetic testing and colonoscopy is recommended for people with a strong history of colorectal cancer (CRC). However, families must communicate so that all members are aware of the risk. The study aimed to explore the factors influencing family communication about genetic risk and colonoscopy among people with a strong family history of CRC who attended a genetic clinic with a view to having a genetic test for hereditary non-polyposis colon cancer (HNPCC).

Hereditary ataxias and paediatric neurology: new movers and shakers enter the field

Over 25 autosomal dominant and autosomal recessive spinocerebellar ataxias have been isolated over the last decade. The recognition of paediatric ataxia phenotypes and, in addition, other movement disorders including hereditary choreiform and parkinsonian syndromes, has improved our knowledge of these diseases. Advances in molecular genetics has allowed fuller delineation and better recognition of these diseases. (C) 2003 European Paediatric Neurology Society. Published by Elsevier Ltd. All rights reserved.

Trusting Groups in Coalition Formation using Social Distance

In environments where distributed team formation is key, and defections are possible, the use of trust as social capital allows social norms to be defied and compared. An agent can use this information, when invited to join a group or collation, to decide whether or not its utility will be increased by joining. In this work a social network approach is used to define and reason about the relationships contained in the agent community. Previous baseline work is extended with two decision making mechanisms. These are compared by simulating an abstract grid-like environment, and preliminary results are reported.

Mutations in sodium-borate cotransporter SLC4A11 cause recessive congenital hereditary endothelial dystrophy (CHED2)

Congenital hereditary endothelial dystrophy ( CHED) is a heritable, bilateral corneal dystrophy characterized by corneal opacification and nystagmus. We describe seven different mutations in the SLC4A11 gene in ten families with autosomal recessive CHED. Mutations in SLC4A11, which encodes a membrane-bound sodium-borate cotransporter, cause loss of function of the protein either by blocking its membrane targeting or nonsense-mediated decay.

Clinical and molecular characteristics of hereditary non-polyposis colorectal cancer families in Southeast Asia

Hereditary non-polyposis colorectal cancer (HNPCC), predominantly due to germline MLH1/MSH2 mutations, is the commonest form of hereditary colorectal cancer (CRC), but data in Asians are sparse. We sequenced the MLH1/MSH2 coding and promoter core regions in CRC patients diagnosed below age 40, and/or with multiple primary cancers or familial cancer clustering suggestive of HNPCC, and correlated deleterious mutations with clinical and tumour features. Forty-six Chinese, Malay and Indian kindreds participated. Of the 153 cancers reported in the 46 kindreds, stomach (14%) and urogenital cancers (13%) were the most common extracolonic cancers, whereas endometrial cancer comprised only 7%. Eleven different MLH1 and 12 MSH2 mutations were identified, including nine novel and four recurring mutations in the Chinese. One Indian was a compound heterozygote for an MLH1 and MSH2 mutation. The MLH1/MSH2 mutation data in the Malays and the Indians represents the first in these ethnic groups. Factors strongly associated with deleterious mutations were the Amsterdam criteria, family history of stomach or multiple primary cancers, and MSI-high tumours, whereas family history of endometrial cancer and young cancer age alone correlated poorly. Distinct clinical and molecular characteristics were identified among Asian HNPCC kindreds and may have important clinical implications.

Detecting Anomalies in Graphs with Numeric Labels

This paper presents Yagada, an algorithm to search labelled graphs for anomalies using both structural data and numeric attributes. Yagada is explained using several security-related examples and validated with experiments on a physical Access Control database. Quantitative analysis shows that in the upper range of anomaly thresholds, Yagada detects twice as many anomalies as the best-performing numeric discretization algorithm. Qualitative evaluation shows that the detected anomalies are meaningful, representing a com- bination of structural irregularities and numerical outliers.

Structural similarity of directed universal hierarchical graphs: A low computational complexity approach

In the present paper we mainly introduce an efficient approach to measure the structural similarity of so called directed universal hierarchical graphs. We want to underline that directed universal hierarchical graphs can be obtained from generalized trees which are already introduced. In order to classify these graphs, we state our novel graph similarity method. As a main result we notice that our novel algorithm has low computational complexity. (c) 2007 Elsevier Inc. All rights reserved.

A comparative analysis of multidimensional features of objects resembling sets of graphs

In the present paper, we introduce a notion of a style representing abstract, complex objects having characteristics that can be represented as structured objects. Furthermore, we provide some mathematical properties of such styles. As a main result, we present a novel approach to perform a meaningful comparative analysis of such styles by defining and using graph-theoretic measures. We compare two styles by comparing the underlying feature sets representing sets of graph structurally. To determine the structural similarity between the underlying graphs, we use graph similarity measures that are computationally efficient. More precisely, in order to compare styles, we map each feature set to a so-called median graph and compare the resulting median graphs. As an application, we perform an experimental study to compare special styles representing sets of undirected graphs and present numerical results thereof. (C) 2007 Elsevier Inc. All rights reserved.

Topological mappings between graphs, trees and generalized trees

We present novel topological mappings between graphs, trees and generalized trees that means between structured objects with different properties. The two major contributions of this paper are, first, to clarify the relation between graphs, trees and generalized trees, a graph class recently introduced. Second, these transformations provide a unique opportunity to transform structured objects into a representation that might be beneficial for a processing, e.g., by machine learning techniques for graph classification. (c) 2006 Elsevier Inc. All rights reserved.

Short distance phase shifts revisited: tracking clock-shifted homing pigeons (Rock Dove Columba livia) close to the loft

Clock-shifted homing pigeons (Rock Dove Columba livia) were tracked from familiar release sites using a direction recorder. At relatively short distances from the home loft (

Distance limits to intermediate- and high-velocity clouds

We present optical spectra of 403 stars and quasi-stellar objects in order to obtain distance limits towards intermediate- and high-velocity clouds (IHVCs), including new Fibre-fed Extended Range Optical Spectrograph (FEROS) observations plus archival ELODIE, FEROS, High Resolution Echelle Spectrometer (HIRES) and Ultraviolet and Visual Echelle Spectrograph (UVES) data. The non-detection of Ca II K interstellar (IS) absorption at a velocity of −130 to −60 km s−1 towards HDE 248894 (d ∼ 3 kpc) and HDE 256725 (d ∼ 8 kpc) in data at signal-to-noise ratio (S/N) > 450 provides a new firm lower distance limit of 8 kpc for the anti-centre shell HVC. Similarly, the non-detection of Ca II K IS absorption towards HD 86248 at S/N ∼ 500 places a lower distance limit of 7.6 kpc for Complex EP, unsurprising since this feature is probably related to the Magellanic System. The lack of detection of Na I D at S/N = 35 towards Mrk 595 puts an improved upper limit for the Na I column density of log (NNaD <) 10.95 cm−2 towards this part of the Cohen Stream where Ca II was detected by Wakker et al. Absorption at ∼ −40 km s−1 is detected in Na I D towards the Galactic star PG 0039+049 at S/N = 75, placing a firm upper distance limit of 1 kpc for the intermediate-velocity cloud south (IVS), where a tentative detection had previously been obtained by Centurion et al. Ca ´ II K and Na I D absorption is detected at −53 km s−1 towards HD 93521, which confirms the upper distance limit of 2.4 kpc for part of the IV arch complex obtained using the International Ultraviolet Explorer (IUE) data by Danly. Towards HD 216411 in Complex H a non-detection in Na D towards gas with log(NH I) = 20.69 cm−2 puts a lower distance limit of 6.6 kpc towards this HVC complex. Additionally, Na I D absorption is detected at −43.7 km s−1 in the star HD 218915 at a distance of 5.0 kpc in gas in the same region of the sky as Complex H. Finally, the Na I/Ca II and Ca II/H I ratios of the current sample are found to lie in the range observed for previous studies of IHVCs.