Computational problems in perfect phylogeny haplotyping: Typing without calling the allele

A haplotype is an m-long binary vector. The XOR-genotype of two haplotypes is the m-vector of their coordinate-wise XOR. We study the following problem: Given a set of XOR-genotypes, reconstruct their haplotypes so that the set of resulting haplotypes can be mapped onto a perfect phylogeny (PP) tree. The question is motivated by studying population evolution in human genetics and is a variant of the PP haplotyping problem that has received intensive attention recently. Unlike the latter problem, in which the input is '' full '' genotypes, here, we assume less informative input and so may be more economical to obtain experimentally. Building on ideas of Gusfield, we show how to solve the problem in polynomial time by a reduction to the graph realization problem. The actual haplotypes are not uniquely determined by the tree they map onto and the tree itself may or may not be unique. We show that tree uniqueness implies uniquely determined haplotypes, up to inherent degrees of freedom, and give a sufficient condition for the uniqueness. To actually determine the haplotypes given the tree, additional information is necessary. We show that two or three full genotypes suffice to reconstruct all the haplotypes and present a linear algorithm for identifying those genotypes.

EEG-based functional networks in schizophrenia.

Schizophrenia is often considered as a dysconnection syndrome in which, abnormal interactions between large-scale functional brain networks result in cognitive and perceptual deficits. In this article we apply the graph theoretic measures to brain functional networks based on the resting EEGs of fourteen schizophrenic patients in comparison with those of fourteen matched control subjects. The networks were extracted from common-average-referenced EEG time-series through partial and unpartial cross-correlation methods. Unpartial correlation detects functional connectivity based on direct and/or indirect links, while partial correlation allows one to ignore indirect links. We quantified the network properties with the graph metrics, including mall-worldness, vulnerability, modularity, assortativity, and synchronizability. The schizophrenic patients showed method-specific and frequency-specific changes especially pronounced for modularity, assortativity, and synchronizability measures. However, the differences between schizophrenia patients and normal controls in terms of graph theory metrics were stronger for the unpartial correlation method.

Iowa’s Bridge and Highway Climate Change and Extreme Weather Vulnerability Assessment Pilot, HEPN-707, 2015

The Iowa Department of Transportation (DOT) is responsible for approximately 4,100 bridges and structures that are a part of the state’s primary highway system, which includes the Interstate, US, and Iowa highway routes. A pilot study was conducted for six bridges in two Iowa river basins—the Cedar River Basin and the South Skunk River Basin—to develop a methodology to evaluate their vulnerability to climate change and extreme weather. The six bridges had been either closed or severely stressed by record streamflow within the past seven years. An innovative methodology was developed to generate streamflow scenarios given climate change projections. The methodology selected appropriate rainfall projection data to feed into a streamflow model that generated continuous peak annual streamflow series for 1960 through 2100, which were used as input to PeakFQ to estimate return intervals for floods. The methodology evaluated the plausibility of rainfall projections and credibility of streamflow simulation while remaining consistent with U.S. Geological Survey (USGS) protocol for estimating the return interval for floods. The results were conveyed in an innovative graph that combined historical and scenario-based design metrics for use in bridge vulnerability analysis and engineering design. The pilot results determined the annual peak streamflow response to climate change likely will be basin-size dependent, four of the six pilot study bridges would be exposed to increased frequency of extreme streamflow and would have higher frequency of overtopping, the proposed design for replacing the Interstate 35 bridges over the South Skunk River south of Ames, Iowa is resilient to climate change, and some Iowa DOT bridge design policies could be reviewed to consider incorporating climate change information.

Statistical Summaries of Selected Iowa Streamflow Data Through September 1996, HR-395, 1998

Statistical summaries of streamflow data collected at 156 streamflow-gaging stations in Iowa are presented in this report. All gaging stations included for analysis have at least 10 years of continuous record collected before or through September 1996. The statistical summaries include (1) statistics of monthly and annual mean discharges; (2) monthly and annual flow durations; (3) magnitudes and frequencies of instantaneous peak discharges (flood frequencies); and (4) magnitudes and frequencies of high and low discharges. Also presented for each gaging station is a graph of the annual mean flows and, for most stations, selected values from the most-recent stage-discharge rating table.

Cardiac motion estimation by joint alignment of tagged MRI sequences

Image registration has been proposed as an automatic method for recovering cardiac displacement fields from Tagged Magnetic Resonance Imaging (tMRI) sequences. Initially performed as a set of pairwise registrations, these techniques have evolved to the use of 3D+t deformation models, requiring metrics of joint image alignment (JA). However, only linear combinations of cost functions defined with respect to the first frame have been used. In this paper, we have applied k-Nearest Neighbors Graphs (kNNG) estimators of the -entropy (H ) to measure the joint similarity between frames, and to combine the information provided by different cardiac views in an unified metric. Experiments performed on six subjects showed a significantly higher accuracy (p < 0.05) with respect to a standard pairwise alignment (PA) approach in terms of mean positional error and variance with respect to manually placed landmarks. The developed method was used to study strains in patients with myocardial infarction, showing a consistency between strain, infarction location, and coronary occlusion. This paper also presentsan interesting clinical application of graph-based metric estimators, showing their value for solving practical problems found in medical imaging.

Real-time, in vivo intracellular recordings of caterpillar-induced depolarization waves in sieve elements using aphid electrodes.

Plants propagate electrical signals in response to artificial wounding. However, little is known about the electrophysiological responses of the phloem to wounding, and whether natural damaging stimuli induce propagating electrical signals in this tissue. Here, we used living aphids and the direct current (DC) version of the electrical penetration graph (EPG) to detect changes in the membrane potential of Arabidopsis sieve elements (SEs) during caterpillar wounding. Feeding wounds in the lamina induced fast depolarization waves in the affected leaf, rising to maximum amplitude (c. 60 mV) within 2 s. Major damage to the midvein induced fast and slow depolarization waves in unwounded neighbor leaves, but only slow depolarization waves in non-neighbor leaves. The slow depolarization waves rose to maximum amplitude (c. 30 mV) within 14 s. Expression of a jasmonate-responsive gene was detected in leaves in which SEs displayed fast depolarization waves. No electrical signals were detected in SEs of unwounded neighbor leaves of plants with suppressed expression of GLR3.3 and GLR3.6. EPG applied as a novel approach to plant electrophysiology allows cell-specific, robust, real-time monitoring of early electrophysiological responses in plant cells to damage, and is potentially applicable to a broad range of plant-herbivore interactions.

Localitzador gràfic d'adreces IP

Internet s'ha convertit en una font extraordinària de recursos per una audiència en constant creixement arreu el món. A l'igual que en altres activitats de la nostra societat, el coneixement de la localització geogràfica d'aquests recursos i de la gent que hi accedeix és útil tant pels usuaris com pels proveïdors d'informació. La geolocalització IP, però, pot donar informació errònia o amb un nivell de precisió que no vagi més enllà de la referència a un país.Aquest treball recull els diferents actors que formen part de la geolocalització IP i s'ha analitzat el paper que juguen en aquest procés així com la seva influència en el nivell de fiabilitat i exactitud final. Amb aquests sòlids fonaments s'ha desenvolupat una aplicació per representar gràficament en un mapa la geolocalització IP d'un dispositiu i la dels nodes que formen el camí realitzat fins arribar-hi, així com tota la informació addicional que de cada IP s'ha pogut obtenir.El resultat ha estat una memòria tècnica de tot el treball de recerca juntament amb una aplicació que s'executa en l'entorn de Microsoft Windows i plataforma .NET, caracteritzada per la seva facilitat d'ús gràcies a un disseny simple molt intuïtiu i efectiu, la rapidesa d'execució per què aprofita la programació de fils, i un positiu impacte visual ja que fa servir l'API de Google Maps per a la representació visual de la traça.

Improving T2 -weighted imaging at high field through the use of kT -points.

PURPOSE: At high magnetic field strengths (B0 ≥ 3 T), the shorter radiofrequency wavelength produces an inhomogeneous distribution of the transmit magnetic field. This can lead to variable contrast across the brain which is particularly pronounced in T2 -weighted imaging that requires multiple radiofrequency pulses. To obtain T2 -weighted images with uniform contrast throughout the whole brain at 7 T, short (2-3 ms) 3D tailored radiofrequency pulses (kT -points) were integrated into a 3D variable flip angle turbo spin echo sequence. METHODS: The excitation and refocusing "hard" pulses of a variable flip angle turbo spin echo sequence were replaced with kT -point pulses. Spatially resolved extended phase graph simulations and in vivo acquisitions at 7 T, utilizing both single channel and parallel-transmit systems, were used to test different kT -point configurations. RESULTS: Simulations indicated that an extended optimized k-space trajectory ensured a more homogeneous signal throughout images. In vivo experiments showed that high quality T2 -weighted brain images with uniform signal and contrast were obtained at 7 T by using the proposed methodology. CONCLUSION: This work demonstrates that T2 -weighted images devoid of artifacts resulting from B1 (+) inhomogeneity can be obtained at high field through the optimization of extended kT -point pulses. Magn Reson Med 71:1478-1488, 2014. © 2013 Wiley Periodicals, Inc.

Diffusion dynamics on multiplex networks

We study the time scales associated with diffusion processes that take place on multiplex networks, i.e., on a set of networks linked through interconnected layers. To this end, we propose the construction of a supra-Laplacian matrix, which consists of a dimensional lifting of the Laplacian matrix of each layer of the multiplex network. We use perturbative analysis to reveal analytically the structure of eigenvectors and eigenvalues of the complete network in terms of the spectral properties of the individual layers. The spectrum of the supra-Laplacian allows us to understand the physics of diffusionlike processes on top of multiplex networks.

Deciphering the global organization of clustering in real complex networks

We uncover the global organization of clustering in real complex networks. To this end, we ask whether triangles in real networks organize as in maximally random graphs with given degree and clustering distributions, or as in maximally ordered graph models where triangles are forced into modules. The answer comes by way of exploring m-core landscapes, where the m-core is defined, akin to the k-core, as the maximal subgraph with edges participating in at least m triangles. This property defines a set of nested subgraphs that, contrarily to k-cores, is able to distinguish between hierarchical and modular architectures. We find that the clustering organization in real networks is neither completely random nor ordered although, surprisingly, it is more random than modular. This supports the idea that the structure of real networks may in fact be the outcome of self-organized processes based on local optimization rules, in contrast to global optimization principles.

Local optima networks of hard combinatorial landscapes

Combinatorial optimization involves finding an optimal solution in a finite set of options; many everyday life problems are of this kind. However, the number of options grows exponentially with the size of the problem, such that an exhaustive search for the best solution is practically infeasible beyond a certain problem size. When efficient algorithms are not available, a practical approach to obtain an approximate solution to the problem at hand, is to start with an educated guess and gradually refine it until we have a good-enough solution. Roughly speaking, this is how local search heuristics work. These stochastic algorithms navigate the problem search space by iteratively turning the current solution into new candidate solutions, guiding the search towards better solutions. The search performance, therefore, depends on structural aspects of the search space, which in turn depend on the move operator being used to modify solutions. A common way to characterize the search space of a problem is through the study of its fitness landscape, a mathematical object comprising the space of all possible solutions, their value with respect to the optimization objective, and a relationship of neighborhood defined by the move operator. The landscape metaphor is used to explain the search dynamics as a sort of potential function. The concept is indeed similar to that of potential energy surfaces in physical chemistry. Borrowing ideas from that field, we propose to extend to combinatorial landscapes the notion of the inherent network formed by energy minima in energy landscapes. In our case, energy minima are the local optima of the combinatorial problem, and we explore several definitions for the network edges. At first, we perform an exhaustive sampling of local optima basins of attraction, and define weighted transitions between basins by accounting for all the possible ways of crossing the basins frontier via one random move. Then, we reduce the computational burden by only counting the chances of escaping a given basin via random kick moves that start at the local optimum. Finally, we approximate network edges from the search trajectory of simple search heuristics, mining the frequency and inter-arrival time with which the heuristic visits local optima. Through these methodologies, we build a weighted directed graph that provides a synthetic view of the whole landscape, and that we can characterize using the tools of complex networks science. We argue that the network characterization can advance our understanding of the structural and dynamical properties of hard combinatorial landscapes. We apply our approach to prototypical problems such as the Quadratic Assignment Problem, the NK model of rugged landscapes, and the Permutation Flow-shop Scheduling Problem. We show that some network metrics can differentiate problem classes, correlate with problem non-linearity, and predict problem hardness as measured from the performances of trajectory-based local search heuristics.

The Case for Linking World Law Data

The present paper advocates for the creation of a federated, hybrid database in the cloud, integrating law data from all available public sources in one single open access system - adding, in the process, relevant meta-data to the indexed documents, including the identification of social and semantic entities and the relationships between them, using linked open data techniques and standards such as RDF. Examples of potential benefits and applications of this approach are also provided, including, among others, experiences from of our previous research, in which data integration, graph databases and social and semantic networks analysis were used to identify power relations, litigation dynamics and cross-references patterns both intra and inter-institutionally, covering most of the World international economic courts.

Algoritmos genéticos para la anonimización de grafos

Peer-reviewed