Efficient metabolism in bioengineered tissues requires a robust vascular system to provide healthy microenvironments to the cells and stroma. Such networks form spontaneously during embryogenesis from randomly distributed endothelial cells. There is a need to bioengineer endothelial cells so that network formation and operation is optimal for synthetic tissues. This work introduces a computational model that simulates de novo vascular development and assesses the effectiveness of the network in delivering nutrients and extracting waste from tissue. A genetic algorithm was employed to identify parameter values of the vaculogenesis model that lead to the most efficient and robust vascular structures. These parameter values control the behavior of cell-level mechanisms such as chemotaxis and adhesion. These studies demonstrate that genetic algorithms are effective at identifying model parameters that lead to near-optimal networks. This work suggests that computational modeling and optimization approaches may improve the effectiveness of engineered tissues by suggesting target cellular mechanisms for modification.

Multiscale models that link sub-cellular, cellular and multicellular components offer powerful insights in disease development. Such models need a realistic set of parameters to represent the physical and chemical mechanisms at the sub-cellular and cellular levels to produce high fidelity multicellular outcomes. However, determining correct values for some of the parameters is often difficult and expensive using high-throughput microfluidic approaches. This work presents an alternative approach that estimates cellular parameters from spatiotemporal data produced from bioengineered multicellular in vitro experiments. Specifically, we apply a search technique to an integrated cellular and multicellular model of retinal pigment epithelial (RPE) cells to estimate the binding rate and auto-regulation rate of vascular endothelial growth factor (VEGF). Understanding VEGF regulation is critical in treating age-related macular degeneration and many other diseases. The method successfully identifies realistic values for autoregulatory cellular parameters that reproduce the spatiotemporal in vitro experimental data.

MOTIVATION: Biological system behaviors are often the outcome of complex interactions among a large number of cells and their biotic and abiotic environment. Computational biologists attempt to understand, predict and manipulate biological system behavior through mathematical modeling and computer simulation. Discrete agent-based modeling (in combination with high-resolution grids to model the extracellular environment) is a popular approach for building biological system models. However, the computational complexity of this approach forces computational biologists to resort to coarser resolution approaches to simulate large biological systems. High-performance parallel computers have the potential to address the computing challenge, but writing efficient software for parallel computers is difficult and time-consuming. RESULTS: We have developed Biocellion, a high-performance software framework, to solve this computing challenge using parallel computers. To support a wide range of multicellular biological system models, Biocellion asks users to provide their model specifics by filling the function body of pre-defined model routines. Using Biocellion, modelers without parallel computing expertise can efficiently exploit parallel computers with less effort than writing sequential programs from scratch. We simulate cell sorting, microbial patterning and a bacterial system in soil aggregate as case studies. AVAILABILITY AND IMPLEMENTATION: Biocellion runs on x86 compatible systems with the 64 bit Linux operating system and is freely available for academic use. Visit http://biocellion.com for additional information.

BACKGROUND: Cellular differentiation during development is controlled by gene regulatory networks (GRNs). This complex process is always subject to gene expression noise. There is evidence suggesting that commonly seen patterns in GRNs, referred to as biological multistable switches, play an important role in creating the structure of lineage trees by providing stability to cell types. RESULTS: To explore this question a new methodology is developed and applied to study (a) the multistable switch-containing GRN for hematopoiesis and (b) a large set of random boolean networks (RBNs) in which multistable switches were embedded systematically. In this work, each network attractor is taken to represent a distinct cell type. The GRNs were seeded with one or two identical copies of each multistable switch and the effect of these additions on two key aspects of network dynamics was assessed. These properties are the barrier to movement between pairs of attractors (separation) and the degree to which one direction of movement between attractor pairs is favored over another (directionality). Both of these properties are instrumental in shaping the structure of lineage trees. We found that adding one multistable switch of any type had a modest effect on increasing the proportion of well-separated attractor pairs. Adding two identical switches of any type had a much stronger effect in increasing the proportion of well-separated attractors. Similarly, there was an increase in the frequency of directional transitions between attractor pairs when two identical multistable switches were added to GRNs. This effect on directionality was not observed when only one multistable switch was added. CONCLUSIONS: This work provides evidence that the occurrence of multistable switches in networks that control cellular differentiation contributes to the structure of lineage trees and to the stabilization of cell types.

BACKGROUND: Analysis of cellular processes with microscopic bright field defocused imaging has the advantage of low phototoxicity and minimal sample preparation. However bright field images lack the contrast and nuclei reporting available with florescent approaches and therefore present a challenge to methods that segment and track the live cells. Moreover, such methods must be robust to systemic and random noise, variability in experimental configuration, and the multiple unknowns in the biological system under study. RESULTS: A new method called maximal-information is introduced that applies a non-parametric information theoretic approach to segment bright field defocused images. The method utilizes a combinatorial optimization strategy to select specific defocused images from each image stack such that set complexity, a Kolmogorov complexity measure, is maximized. Differences among these selected images are then applied to initialize and guide a level set based segmentation algorithm. The performance of the method is compared with a recent approach that uses a fixed defocused image selection strategy over an image data set of embryonic kidney cells (HEK 293T) from multiple experiments. Results demonstrate that the adaptive maximal-information approach significantly improves precision and recall of segmentation over the diversity of data sets. CONCLUSIONS: Integrating combinatorial optimization with non-parametric Kolmogorov complexity has been shown to be effective in extracting information from microscopic bright field defocused images. The approach is application independent and has the potential to be effective in processing a diversity of noisy and redundant high throughput biological data.

Computational modeling has the potential to bridge the knowledge gap between the identification of cellular mechanisms altered in cancer and understanding development of the disease. A multicellular Glazier-Granier-Hogeweg (GGH)-based model that considers biologically realistic parameters of endothelial cells and the extracellular matrix was developed and used to explore how tumors induce angiogenesis. The effect on angiogenesis of modifying these parameters singly and in combination was examined in a massively parallel search to discover novel therapeutic approaches. A two phase search process was employed: First random restart hill climbing identified potentially valuable points within the search space, then multi-dimensional parameter sweeps were performed over the nearby region to further refine solution quality. Examples of combination therapies to block nutrient delivery to the tumor that were discovered in the search are presented. Multicellular modeling to identify potential cancer chemotherapies is a promising approach to reveal new targets for cancer drug development and testing.

Solid tumors must recruit new blood vessels for growth and maintenance. Discovering drugs that block tumor-induced development of new blood vessels (angiogenesis) is an important approach in cancer treatment. The complexity of angiogenesis presents both challenges and opportunities for cancer therapies. Intuitive approaches, such as blocking VegF activity, have yielded important therapies. But there maybe opportunities to alter nonintuitive targets either alone or in combination. This paper describes the development of a high-fidelity simulation of angiogenesis and uses this as the basis for a parallel search-based approach for the discovery of novel potential cancer treatments that inhibit blood vessel growth. Discovering new therapies is viewed as a multiobjective combinatorial optimization over two competing objectives: minimizing the estimated cost of practically developing the intervention while minimizing the simulated oxygen provided to the tumor by angiogenesis. Results show the effectiveness of the search process by finding interventions that are currently in use, and more interestingly, discovering potential new approaches that are nonintuitive yet effective.

Sorting by reversals is a simplified version of the genome rearrangement problem that seeks to discover the evolutionary relationship between different genomes, and is one of the many challenging problems in Bioinformatics. Solving the problem optimally has been proved to be NP-Hard and so a selection of approximation algorithms have been developed. In this paper a new mapping order is introduced to solve the problem of sorting unsigned permutations using a specialized multi-objective genetic algorithm. Our modified genetic algorithm uses a population with variable length individuals to maintain a worst time running time complexity of 0(n4log2n), where n is the problem size. The results show that this approach is more effective than the 3/2 heuristic method and previous genetic algorithm approaches.

Solid tumors must recruit new blood vessels for growth and maintenance. Discovering drugs that block this tumor-induced development of new blood vessels (angiogenesis) is an important approach in cancer treatment. However, the complexity of angiogenesis and the difficulty in implementing and evaluating rationally-designed treatments prevent the discovery of effective new therapies. This paper presents a massively parallel computational search-based approach for the discovery of novel potential cancer treatments using a high fidelity simulation of angiogenesis. Discovering new therapies is viewed as multi-objective combinatorial optimization over two competing objectives: minimizing the cost of developing the intervention while minimizing the oxygen provided to the cancer tumor by angiogenesis. Results show the effectiveness of the search process in finding interventions that are currently in use and more interestingly, discovering some new approaches that are counter intuitive yet effective.

We used a computational approach to examine three questions at the intersection of developmental biology and evolution: 1) What is the space available for evolutionary exploration for genetic regulatory networks (GRNs) able to solve developmental patterning problems? 2) If different GRNs exist that can solve a particular pattern, are there differences between them that might lead to the selection of one over another? 3) What are the possibilities for co-opting GRN subcircuits or even entire GRNs evolved to solve one pattern for use in the solution of another pattern? We used a Monte Carlo strategy to search for simulated GRNs composed of nodes (proteins) and edges (regulatory interactions between proteins) capable of solving one of three striped cellular patterning problems. These GRNs were subjected to a knockout procedure akin to gene knock-outs in genetic research. Knockout was continued until all individual network components of the reduced GRN were shown to be essential for function. This GRN was termed irreducible. We found many different unique irreducible GRNs that were able to solve each patterning problem. Since any functional GRN must include an irreducible GRN as a core or subgraph, the space for evolutionary exploration of pattern-forming GRNs is large. Irreducible GRNs that solve a particular pattern differed widely in their robustness - the ability to solve a target pattern under different initial conditions. These differences may offer a target for selection to winnow out less robust GRNs from the set of GRNs found in nature. Finally, subgraph isomorphism analysis revealed great potential for co-option during evolution. Some irreducible GRNs appear in their entirety within larger GRNs that solve different patterning problems. At much higher frequency, subcycles are shared widely among irreducible GRNs, including those that solve different patterns. Irreducible GRNs may form the core elements of GRNs found in biological systems and provide insight into their evolution

Area coverage operations such as plowing a field or mowing a lawn can be performed faster if multiple vehicles are involved. To use a team of automated vehicles safely and effectively they must be coordinated to avoid collisions and deadlock situations. Unexpected events may occur during the operation which may affect vehicles' velocities, so the coordination method must be robust with respect to these events. In this paper, a path coordination method is introduced which delays decisions about mission coordination as long as possible during mission execution so such unexpected situations are efficiently handled. The method's computation speed and solution quality are evaluated through simulation, and compared with two other methods based on common path coordination techniques.

Many significant engineering and scientific problems involve optimization of some criteria over a combinatorial configuration space. The two methods most often used to solve these problems effectively-simulated annealing (SA) and genetic algorithms (GA)-do not easily lend themselves to massive parallel implementations. Simulated annealing is a naturally serial algorithm, while GA involves a selection process that requires global coordination. This paper introduces a new hybrid algorithm that inherits those aspects of GA that lend themselves to parallelization, and avoids serial bottle-necks of GA approaches by incorporating elements of SA to provide a completely parallel, easily scalable hybrid GA/SA method. This new method, called Genetic Simulated Annealing, does not require parallelization of any problem specific portions of a serial implementation-existing serial implementations can be incorporated as is. Results of a study on two difficult combinatorial optimization problems, a 100 city traveling salesperson problem and a 24 word, 12 bit error correcting code design problem, performed on a 16 K PE MasPar MP-1, indicate advantages over previous parallel GA and SA approaches. One of the key results is that the performance of the algorithm scales up linearly with the increase of processing elements, a feature not demonstrated by any previous parallel GA or SA approaches, which enables the new algorithm to utilize massive parallel architecture with maximum effectiveness. Additionally, the algorithm does not require careful choice of control parameters, a significant advantage over SA and GA.

The principal advantage of incremental A* algorithms for precomputing and maintaining routes for mobile robotic vehicles is the completeness and optimality of the approach. However, the computational burden becomes unreasonable when large worlds are modeled or fine resolution is required, since the complexity is bound by the area modeled. This problem is compounded when multiple vehicles and multiple goals are involved, since routes to each goal from each vehicle must be maintained. This paper presents a massively parallel incremental A* algorithm suitable for implementing in VLSI. The number of iterations of the parallel algorithm is bound by the optimal path length, providing a significant speedup for large worlds. Empirical studies combined with a feasible VLSI design estimate that path calculations on a 1000 by 1000 world could be done in approximately 110 mS worse case.