Non-self-adjoint graphs

On finite metric graphs we consider Laplace operators, subject to various classes of non-self-adjoint boundary conditions imposed at graph vertices. We investigate spectral properties, existence of a Riesz basis of projectors and similarity transforms to self-adjoint Laplacians. Among other things, we describe a simple way to relate the similarity transforms between Laplacians on certain graphs with elementary similarity transforms between matrices defining the boundary conditions.

Structural conservations and diversities of dsRNA viruses: Structural studies of the cytoplasmic polyhedrosis virus by electron cryomicroscopy and 3D reconstruction

The Reoviridae virus family is a group of economically and pathologically important viruses that have either single-, double-, or triple-shelled protein layers enclosing a segmented double stranded RNA genome. Each virus particle in this family has its own viral RNA dependent RNA polymerase and the enzymatic activities necessary for the mature RNA synthesis. Based on the structure of the inner most cores of the viruses, the Reoviridae viruses can be divided into two major groups. One group of viruses has a smooth surfaced inner core, surrounded by complete outer shells of one or two protein layers. The other group has an inner core decorated with turrets on the five-fold vertices, and could either completely lack or have incomplete outer protein layers. The structural difference is one of the determinant factors for their biological differences during the infection. ^ Cytoplasmic polyhedrosis virus (CPV) is a single-shelled, turreted virus and the structurally simplest member in Reoviridae. It causes specific chronic infections in the insect gut epithelial cells. Due to its wide range of insect hosts, CPV has been engineered as a potential insecticide for use in fruit and vegetable farming. Its unique structural simplicity, unparalleled capsid stability and ease of purification make CPV an ideal model system for studying the structural basis of dsRNA virus assembly at the highest possible resolution by electron cryomicroscopy (cryoEM) and three-dimensional (3D) reconstruction. ^ In this thesis work, I determined the first 3D structure of CPV capsids using 100 kV cryoEM. At an effective resolution of 17 Å, the full capsid reveals a 600-Å diameter, T = 1 icosahedral shell decorated with A and B spikes at the 5-fold vertices. The internal space of the empty CPV is unoccupied except for 12 mushroom-shaped densities that are attributed to the transcriptional enzyme complexes. The inside of the full capsid is packed with icosahedrally-ordered viral genomic RNA. The interactions of viral RNA with the transcriptional enzyme complexes and other capsid proteins suggest a mechanism for RNA transcription and subsequent release. ^ Second, the interactions between the turret proteins (TPs) and the major capsid shell protein (CSPs) have been identified through 3D structural comparisons of the intact CPV capsids with the spikeless CPV capsids, which were generated by chemical treatments. The differential effects of these chemical treatment experiments also indicated that CPV has a significantly stronger structural integrity than other dsRNA viruses, such as the orthoreovirus subcores, which are normally enclosed within outer protein shells. ^ Finally, we have reconstructed the intact CPV to an unprecendented 8 Å resolution from several thousand of 400kV cryoEM images. The 8 Å structure reveals interactions among the 120 molecules of each of the capsid shell protein (CSP), the large protrusion protein (LPP), and 60 molecules of the turret protein (TP). A total of 1980 α-helices and 720 β-sheets have been identified in these capsid proteins. The CSP structure is largely conserved, with the majority of the secondary structures homologous to those observed in the x-ray structures of corresponding proteins of other reoviruses, such as orthoreovirus and bluetongue virus. The three domains of TP are well positioned to play multifunctional roles during viral transcription. The completely non-equivalent interactions between LPP and CSP and those between the anchoring domain of TP and CSP account for the unparalleled stability of this structurally simplest member of the Reoviridae. ^

A new DSATUR-based algorithm for exact vertex coloring

This paper describes a new exact algorithm PASS for the vertex coloring problem based on the well known DSATUR algorithm. At each step DSATUR maximizes saturation degree to select a new candidate vertex to color, breaking ties by maximum degree w.r.t. uncolored vertices. Later Sewell introduced a new tiebreaking strategy, which evaluated available colors for each vertex explicitly. PASS differs from Sewell in that it restricts its application to a particular set of vertices. Overall performance is improved when the new strategy is applied selectively instead of at every step. The paper also reports systematic experiments over 1500 random graphs and a subset of the DIMACS color benchmark.

De la ciudad en vibración al ser resonante: Una investigación a propósito de los conciertos de campanas de Llorenç Barber

Este trabajo tiene la vocación de dibujar el mapa de los dominios de oportunidad que hay a disposición de un arquitecto, al imaginar el aspecto sonoro de la ciudad en relación con la campana. Muchas de las dimensiones señaladas, tanto conocidas como desconocidas, son sencillamente despertadas al estudio de lo que un diseñador del espacio sonoro, como Llorenç Barber, viene a decirnos, desde una disciplina aparentemente contactada, pero muchas veces paralela a la arquitectónica. Tomando los conciertos de campanas celebrados hasta la fecha como puestas en práctica real de la condición instrumental de más de doscientas ciudades de todo el mundo, el estudio analiza los hallazgos, éxitos y fracasos, obtenidos a lo largo de estos últimos veinticinco años de experiencia, como resultados explícitos de un trabajo sonoro en la ciudad, probado, contrastado y afinado, del que extraer indicaciones concretas susceptibles de ser aplicadas en el diseño del espacio urbano. Mediante un análisis triangular de vértices definidos: emisor-campana, medio-ciudad, receptor-ciudadano; la investigación aborda los aspectos relativos a la producción y recepción del fenómeno sonoro generado por la campana en la ciudad. En relación con la producción, una parte del trabajo se dedica al estudio de los efectos acústicos observados, ordenado por escalas graduales en las que se produce una distribución del sonido susceptible de diseño: el vaso de la campana, la sala de campanas, el campanario, el cuerpo del edificio, la ciudad y el territorio. A modo de cajas de resonancia y leídas como muñecas rusas, unas dentro de otras, los espacios identificados muestran cualidades sonoras específicas, definidas tanto por sus condiciones geométricas, formales, constructivas o de uso; como por las correspondientes a las subsiguientes cajas que alojan. A fin de esclarecer la influencia de tales cuestiones en el aspecto sonoro de la ciudad, se propone un modelo ordenado de conexión y desconexión de escalas, utilizando una paramétrica puramente técnica creada ex profeso, junto con variables metodológicas más tradicionales. Al mismo tiempo, y tratando de esclarecer cómo, al ser puesta en vibración, la ciudad es aprehendida, disfrutada y rememorada por el ciudadano-oyente, otra parte del trabajo se dedica al estudio de los aspectos relativos a su recepción aural en deambulación compartida. En este caso la investigación se propone reclamar otras dimensiones más subversivas que, si bien escapan a los modos habituales de trabajar del arquitecto, se revelan intensamente en la experiencia plurifocal, multiplicando los efectos a considerar: efectos funcionales y significativos, de reconocimiento, integración y pertenencia a un cuerpo territorial y social de coordenadas históricas y geográficas de nuevo significadas; efectos perceptuales de inmersión, ubicuidad, temporalidad o inestabilidad; efectos estéticos, de rememoración, interpretación simbólica y recreación poética; e incluso efectos políticos, descubriendo un espacio urbano en continua regeneración, lugar para la exposición en su doble acepción, para la exhibición y el peligro, o como contenedor situacional del más profundo sentido ciudadano. Para afinar la relevancia de lo obtenido en cada una de las dimensiones señaladas, el trabajo se articula en tres aproximaciones graduales: el corpus general de los conciertos celebrados hasta la fecha; los conciertos celebrados en España; los tres conciertos para Madrid: Magna Mater (1991), Festi Clamores (2000) y Aurea Catena (2007). Si bien el modelo propuesto nace a la luz de los conciertos de campanas de Llorenç Barber, a escala de una ciudad entera y con una intención compositiva individual, se entiende que sería útil para el uso ordenado de cualquier profesional interesado en el aspecto sonoro de la ciudad, faceta escasamente atendida, dicho sea de paso, desde la disciplina arquitectónica. ABSTRACT This work has the vocation of drawing out the numerous opportunities an architect has at his disposal, upon imagining the sonorous aspect of the city in relation to the bell. Many of the dimensions indicated, both known and unknown, are just awakened to the study of what a sound space designer, as Llorenç Barber, comes to tell us, from a discipline apparently contacted, but often parallel to the architecture. Taking the bell concerts held so far as actual implementation of the instrumental condition of over two hundred cities around the world, the study analyzes the findings, successes and failures, obtained over the last twenty years of experience, as explicit results of a sound work in the city, tested, verified and refined, from which to extract specific indications that can be applied in the design of urban space. By triangular analyzing of defined vertices: sender-bell, half-city, receptor-citizen; the research addresses issues relating to the production and reception of sound phenomenon generated by the bell in the city. In relation to production, part of the work is devoted to the study of observed acoustic effects, ordered gradual scale which produces a distribution of sound capable of design: the glass of the bell, the bell room, the bell tower and the body of the building, the city and territory. By way of sounding boards and read as if they were Russian dolls, one inside the other, the show spaces identified specific sound qualities, defined both for their geometric, formal, constructive use, such as those for hosting the subsequent boxes. In order to clarify the influence of such issues in the sound aspect of the city, we propose an ordered pattern of connection and disconnection of scales, using a purely parametric technique created on purpose, along with more traditional methodological variables. At the same time, and trying to clarify how, when set in vibration, the city is apprehended, enjoyed and remembered for the citizen-listener, another part of the work is devoted to the study of aspects of aural reception in shared ambulation. In this case the research aims to claim more subversive than other dimensions, but beyond the usual ways in which an architect works, the experience reveals intensely plurifocal multiplying effects to consider: functional effects and significant recognition and integration belonging to a body of territorial and social historical and geographical coordinates of new meaning and perceptual effects of immersion, ubiquity, timeliness or instability; aesthetic effects of recall, interpretation and recreation of symbolic poetic; and even political effects, revealing a continuous urban space regeneration site for the exhibition in its double meaning, for display and danger, or as a citizen sense container. To sharpen the relevance of what was obtained in each of the dimensions mentioned, the work is divided into three incremental approaches: the general corpus of the concerts held so far, the concerts in Spain, the three concerts for Madrid: Magna Mater (1991), Festi Clamores (2000) and Aurea Catena (2007). While the proposed model comes in the light of the bells concert Llorenç Barber, the scale of a whole city and individual compositional intent, it is understood that it would be useful for the orderly use of any professional interested in the sound aspect of the city, an aspect sparsely attended, incidentally, from the architectural discipline.

Spiral optical designs for nonimaging applications

Manufacturing technologies as injection molding or embossing specify their production limits for minimum radii of the vertices or draft angle for demolding, for instance. In some demanding nonimaging applications, these restrictions may limit the system optical efficiency or affect the generation of undesired artifacts on the illumination pattern. A novel manufacturing concept is presented here, in which the optical surfaces are not obtained from the usual revolution symmetry with respect to a central axis (z axis), but they are calculated as free-form surfaces describing a spiral trajectory around z axis. The main advantage of this new concept lies in the manufacturing process: a molded piece can be easily separated from its mold just by applying a combination of rotational movement around axis z and linear movement along axis z, even for negative draft angles. Some of these spiral symmetry examples will be shown here, as well as their simulated results.

Novel free-form optical surface design with spiral symmetry

Manufacturing technologies as injection molding or embossing specify their production limits for minimum radii of the vertices or draft angle for demolding, for instance. These restrictions may limit the system optical efficiency or affect the generation of undesired artifacts on the illumination pattern when dealing with optical design. A novel manufacturing concept is presented here, in which the optical surfaces are not obtained from the usual revolution symmetry with respect to a central axis (z axis), but they are calculated as free-form surfaces describing a spiral trajectory around z axis. The main advantage of this new concept lies in the manufacturing process: a molded piece can be easily separated from its mold just by applying a combination of rotational movement around axis z and linear movement along axis z, even for negative draft angles. The general designing procedure will be described in detail

Spiral nonimaging optical designs

Manufacturing technologies as injection molding or embossing specify their production limits for minimum radii of the vertices or draft angle for demolding, for instance. In some demanding nonimaging applications, these restrictions may limit the system optical efficiency or affect the generation of undesired artifacts on the illumination pattern. A novel manufacturing concept is presented here, in which the optical surfaces are not obtained from the usual revolution symmetry with respect to a central axis (z axis), but they are calculated as free-form surfaces describing a spiral trajectory around z axis. The main advantage of this new concept lies in the manufacturing process: a molded piece can be easily separated from its mold just by applying a combination of rotational movement around axis z and linear movement along axis z, even for negative draft angles. Some of these spiral symmetry examples will be shown here, as well as their simulated results.

Solving the minimum vertex floodlight problem with hybrid metaheuristics

In this paper we propose four approximation algorithms (metaheuristic based), for the Minimum Vertex Floodlight Set problem. Urrutia et al. [9] solved the combinatorial problem, although it is strongly believed that the algorithmic problem is NP-hard. We conclude that, on average, the minimum number of vertex floodlights needed to illuminate a orthogonal polygon with n vertices is n/4,29.

Posibilidades del motor 3D de la Nintendo DS

La consola portátil Nintendo DS es una plataforma de desarrollo muy presente entre la comunidad de desarrolladores independientes, con una extensa y nutrida escena homebrew. Si bien las capacidades 2D de la consola están muy aprovechadas, dado que la mayor parte de los esfuerzos de los creadores amateur están enfocados en este aspecto, el motor 3D de ésta (el que se encarga de representar en pantalla modelos tridimensionales) no lo está de igual manera. Por lo tanto, en este proyecto se tiene en vista determinar las capacidades gráficas de la Nintendo DS. Para ello se ha realizado una biblioteca de funciones en C que permite aprovechar las posibilidades que ofrece la consola en el terreno 3D y que sirve como herramienta para la comunidad homebrew para crear aplicaciones 3D de forma sencilla, dado que se ha diseñado como un sistema modular y accesible. En cuanto al proceso de renderizado se han sacado varias conclusiones. En primer lugar se ha determinado la posibilidad de asignar varias componentes de color a un mismo vértice (color material reactivo a la iluminación, color por vértice directo y color de textura), tanto de forma independiente como simultáneamente, pudiéndose utilizar para aplicar diversos efectos al modelo, como iluminación pre-calculada o simulación de una textura mediante color por vértice, ahorrando en memoria de video. Por otro lado se ha implementado un sistema de renderizado multi-capa, que permite realizar varias pasadas de render, pudiendo, de esta forma, aplicar al modelo una segunda textura mezclada con la principal o realizar un efecto de reflexión esférica. Uno de los principales avances de esta herramienta con respecto a otras existentes se encuentra en el apartado de animación. El renderizador desarrollado permite por un lado animación por transformación, consistente en la animación de mallas o grupos de vértices del modelo mediante el movimiento de una articulación asociada que determina su posición y rotación en cada frame de animación. Por otro lado se ha implementado un sistema de animación por muestreo de vértices mediante el cual se determina la posición de éstos en cada instante de la animación, generando frame a frame las poses que componen el movimiento (siendo este último método necesario cuando no se puede animar una malla por transformación). Un mismo modelo puede contener diferentes esqueletos, animados independientemente entre sí, y cada uno de ellos tener definidas varias costumbres de animación que correspondan a movimientos contextuales diferentes (andar, correr, saltar, etc). Además, el sistema permite extraer cualquier articulación para asociar su transformación a un objeto estático externo y que éste siga el movimiento de la animación, pudiendo así, por ejemplo, equipar un objeto en la mano de un personaje. Finalmente se han implementado varios efectos útiles en la creación de escenas tridimensionales, como el billboarding (tanto esférico como cilíndrico), que restringe la rotación de un modelo para que éste siempre mire a cámara y así poder emular la apariencia de un objeto tridimensional mediante una imagen plana, ahorrando geometría, o emplearlo para realizar efectos de partículas. Por otra parte se ha implementado un sistema de animación de texturas por subimágenes que permite generar efectos de movimiento mediante imágenes, sin necesidad de transformar geometría. ABSTRACT. The Nintendo DS portable console has received great interest within the independent developers’ community, with a huge homebrew scene. The 2D capabilities of this console are well known and used since most efforts of the amateur creators has been focused on this point. However its 3D engine (which handles with the representation of three-dimensional models) is not equally used. Therefore, in this project the main objective is to assess the Nintendo DS graphic capabilities. For this purpose, a library of functions in C programming language has been coded. This library allows the programmer to take advantage of the possibilities that the 3D area brings. This way the library can be used by the homebrew community as a tool to create 3D applications in an easy way, since it has been designed as a modular and accessible system. Regarding the render process, some conclusions have been drawn. First, it is possible to assign several colour components to the same vertex (material colour, reactive to the illumination, colour per vertex and texture colour), independently and simultaneously. This feature can be useful to apply certain effects on the model, such as pre-calculated illumination or the simulation of a texture using colour per vertex, providing video memory saving. Moreover, a multi-layer render system has been implemented. This system allows the programmer to issue several render passes on the same model. This new feature brings the possibility to apply to the model a second texture blended with the main one or simulate a spherical reflection effect. One of the main advances of this tool over existing ones consists of its animation system. The developed renderer includes, on the one hand, transform animation, which consists on animating a mesh or groups of vertices of the model by the movement of an associated joint. This joint determines position and rotation of the mesh at each frame of the animation. On the other hand, this tool also implements an animation system by vertex sampling, where the position of vertices is determined at every instant of the animation, generating the poses that build up the movement (the latter method is mandatory when a mesh cannot be animated by transform). A model can contain multiple skeletons, animated independently, each of them being defined with several animation customs, corresponding to different contextual movements (walk, run, jump, etc). Besides, the system allows extraction of information from any joint in order to associate its transform to a static external object, which will follow the movement of the animation. This way, any object could be equipped, for example, on the hand of a character. Finally, some useful effects for the creation of three-dimensional scenes have been implemented. These effects include billboarding (both spherical and cylindrical), which constraints the rotation of a model so it always looks on the camera's direction. This feature can provide the ability to emulate the appearance of a three-dimensional model through a flat image (saving geometry). It can also be helpful in the implementation of particle effects. Moreover, a texture animation system using sub-images has also been implemented. This system allows the generation of movement by using images as textures, without having to transform geometry.

Watching subgraphs to improve efficiency in maximum clique search

This paper describes a new technique referred to as watched subgraphs which improves the performance of BBMC, a leading state of the art exact maximum clique solver (MCP). It is based on watched literals employed by modern SAT solvers for boolean constraint propagation. In efficient SAT algorithms, a list of clauses is kept for each literal (it is said that the clauses watch the literal) so that only those in the list are checked for constraint propagation when a (watched) literal is assigned during search. BBMC encodes vertex sets as bit strings, a bit block representing a subset of vertices (and the corresponding induced subgraph) the size of the CPU register word. The paper proposes to watch two subgraphs of critical sets during MCP search to efficiently compute a number of basic operations. Reported results validate the approach as the size and density of problem instances rise, while achieving comparable performance in the general case.

Optimizing communication by compression for Multi-GPU Scalable Breadth-First Searches

Debido al creciente aumento del tamaño de los datos en muchos de los actuales sistemas de información, muchos de los algoritmos de recorrido de estas estructuras pierden rendimento para realizar búsquedas en estos. Debido a que la representacion de estos datos en muchos casos se realiza mediante estructuras nodo-vertice (Grafos), en el año 2009 se creó el reto Graph500. Con anterioridad, otros retos como Top500 servían para medir el rendimiento en base a la capacidad de cálculo de los sistemas, mediante tests LINPACK. En caso de Graph500 la medicion se realiza mediante la ejecución de un algoritmo de recorrido en anchura de grafos (BFS en inglés) aplicada a Grafos. El algoritmo BFS es uno de los pilares de otros muchos algoritmos utilizados en grafos como SSSP, shortest path o Betweeness centrality. Una mejora en este ayudaría a la mejora de los otros que lo utilizan. Analisis del Problema El algoritmos BFS utilizado en los sistemas de computación de alto rendimiento (HPC en ingles) es usualmente una version para sistemas distribuidos del algoritmo secuencial original. En esta versión distribuida se inicia la ejecución realizando un particionado del grafo y posteriormente cada uno de los procesadores distribuidos computará una parte y distribuirá sus resultados a los demás sistemas. Debido a que la diferencia de velocidad entre el procesamiento en cada uno de estos nodos y la transfencia de datos por la red de interconexión es muy alta (estando en desventaja la red de interconexion) han sido bastantes las aproximaciones tomadas para reducir la perdida de rendimiento al realizar transferencias. Respecto al particionado inicial del grafo, el enfoque tradicional (llamado 1D-partitioned graph en ingles) consiste en asignar a cada nodo unos vertices fijos que él procesará. Para disminuir el tráfico de datos se propuso otro particionado (2D) en el cual la distribución se haciá en base a las aristas del grafo, en vez de a los vertices. Este particionado reducía el trafico en la red en una proporcion O(NxM) a O(log(N)). Si bien han habido otros enfoques para reducir la transferecnia como: reordemaniento inicial de los vertices para añadir localidad en los nodos, o particionados dinámicos, el enfoque que se va a proponer en este trabajo va a consistir en aplicar técnicas recientes de compression de grandes sistemas de datos como Bases de datos de alto volume o motores de búsqueda en internet para comprimir los datos de las transferencias entre nodos.---ABSTRACT---The Breadth First Search (BFS) algorithm is the foundation and building block of many higher graph-based operations such as spanning trees, shortest paths and betweenness centrality. The importance of this algorithm increases each day due to it is a key requirement for many data structures which are becoming popular nowadays. These data structures turn out to be internally graph structures. When the BFS algorithm is parallelized and the data is distributed into several processors, some research shows a performance limitation introduced by the interconnection network [31]. Hence, improvements on the area of communications may benefit the global performance in this key algorithm. In this work it is presented an alternative compression mechanism. It differs with current existing methods in that it is aware of characteristics of the data which may benefit the compression. Apart from this, we will perform a other test to see how this algorithm (in a dis- tributed scenario) benefits from traditional instruction-based optimizations. Last, we will review the current supercomputing techniques and the related work being done in the area.

Localization of the C terminus of the assembly domain of hepatitis B virus capsid protein: Implications for morphogenesis and organization of encapsidated RNA

The capsid protein of hepatitis B virus, consisting of an “assembly” domain (residues 1–149) and an RNA-binding “protamine” domain (residues 150–183), assembles from dimers into icosahedral capsids of two different sizes. The C terminus of the assembly domain (residues 140–149) functions as a morphogenetic switch, longer C termini favoring a higher proportion of the larger capsids, it also connects the protamine domain to the capsid shell. We now have defined the location of this peptide in capsids assembled in vitro by engineering a mutant assembly domain with a single cysteine at its C terminus (residue 150), labeling it with a gold cluster and visualizing the cluster by cryo-electron microscopy. The labeled protein is unimpaired in its ability to form capsids. Our density map reveals a single undecagold cluster under each fivefold and quasi-sixfold vertex, connected to sites at either end of the undersides of the dimers. Considering the geometry of the vertices, the C termini must be more crowded at the fivefolds. Thus, a bulky C terminus would be expected to favor formation of the larger (T = 4) capsids, which have a greater proportion of quasi-sixfolds. Capsids assembled by expressing the full-length protein in Escherichia coli package bacterial RNAs in amounts equivalent to the viral pregenome. Our density map of these capsids reveals a distinct inner shell of density—the RNA. The RNA is connected to the protein shell via the C-terminal linkers and also makes contact around the dimer axes.

Estimating the probability for a protein to have a new fold: A statistical computational model

Structural genomics aims to solve a large number of protein structures that represent the protein space. Currently an exhaustive solution for all structures seems prohibitively expensive, so the challenge is to define a relatively small set of proteins with new, currently unknown folds. This paper presents a method that assigns each protein with a probability of having an unsolved fold. The method makes extensive use of protomap, a sequence-based classification, and scop, a structure-based classification. According to protomap, the protein space encodes the relationship among proteins as a graph whose vertices correspond to 13,354 clusters of proteins. A representative fold for a cluster with at least one solved protein is determined after superposition of all scop (release 1.37) folds onto protomap clusters. Distances within the protomap graph are computed from each representative fold to the neighboring folds. The distribution of these distances is used to create a statistical model for distances among those folds that are already known and those that have yet to be discovered. The distribution of distances for solved/unsolved proteins is significantly different. This difference makes it possible to use Bayes' rule to derive a statistical estimate that any protein has a yet undetermined fold. Proteins that score the highest probability to represent a new fold constitute the target list for structural determination. Our predicted probabilities for unsolved proteins correlate very well with the proportion of new folds among recently solved structures (new scop 1.39 records) that are disjoint from our original training set.

Pentameric assembly of a neuronal glutamate transporter

Freeze-fracture electron microscopy was used to study the structure of a human neuronal glutamate transporter (EAAT3). EAAT3 was expressed in Xenopus laevis oocytes, and its function was correlated with the total number of transporters in the plasma membrane of the same cells. Function was assayed as the maximum charge moved in response to a series of transmembrane voltage pulses. The number of transporters in the plasma membrane was determined from the density of a distinct 10-nm freeze-fracture particle, which appeared in the protoplasmic face only after EAAT3 expression. The linear correlation between EAAT3 maximum carrier-mediated charge and the total number of the 10-nm particles suggested that this particle represented functional EAAT3 in the plasma membrane. The cross-sectional area of EAAT3 in the plasma membrane (48 ± 5 nm2) predicted 35 ± 3 transmembrane α-helices in the transporter complex. This information along with secondary structure models (6–10 transmembrane α-helices) suggested an oligomeric state for EAAT3. EAAT3 particles were pentagonal in shape in which five domains could be identified. They exhibited fivefold symmetry because they appeared as equilateral pentagons and the angle at the vertices was 110°. Each domain appeared to contribute to an extracellular mass that projects ≈3 nm into the extracellular space. Projections from all five domains taper toward an axis passing through the center of the pentagon, giving the transporter complex the appearance of a penton-based pyramid. The pentameric structure of EAAT3 offers new insights into its function as both a glutamate transporter and a glutamate-gated chloride channel.

Using three-dimensional microfluidic networks for solving computationally hard problems

This paper describes the design of a parallel algorithm that uses moving fluids in a three-dimensional microfluidic system to solve a nondeterministically polynomial complete problem (the maximal clique problem) in polynomial time. This algorithm relies on (i) parallel fabrication of the microfluidic system, (ii) parallel searching of all potential solutions by using fluid flow, and (iii) parallel optical readout of all solutions. This algorithm was implemented to solve the maximal clique problem for a simple graph with six vertices. The successful implementation of this algorithm to compute solutions for small-size graphs with fluids in microchannels is not useful, per se, but does suggest broader application for microfluidics in computation and control.