On the inverse problem in flow cytometry recovering DNA distribution from FMF data

The problem of recovering DNA distribution from cytofluorometric experimental data was investigated. Theoretical analysis led to a convenient formulation of the problem and to uniqueness results for its solution. A minimization algorithm has been implemented to get the optimal estimate of G₁, S, G₂, and M phase percentages. This algorithm was tested in some experimental cases.     

Multi-layered greedy network-growing algorithm: extension of greedy network-growing algorithm to multi-layered networks

In this paper, we extend our greedy network-growing algorithm to multi-layered networks. With multi-layered networks, we can solve many complex problems that single-layered networks fail to solve. In addition, the network-growing algorithm is used in conjunction with teacher-directed learning that produces appropriate outputs without computing errors between targets and outputs. Thus, the present algorithm is a very efficient network-growing algorithm. The new algorithm was applied to three problems: the famous vertical-horizontal lines detection problem, a medical data problem and a road classification problem. In all these cases, experimental results confirmed that the method could solve problems that single-layered networks failed to. In addition, information maximization makes it possible to extract salient features in input patterns.     

基于遗传算法预测2D三向的蛋白质结构

本文基于范德华力势能预测2D三向的蛋白质结构。首先,将蛋白质结构预测这一生物问题转化为数学问题,并建立基于范德华力势能函数的数学模型。其次,使用遗传算法对数学模型进行求解,为了提高蛋白质结构预测效率,我们在标准遗传算法的基础上引入了调整算子这一概念,改进了遗传算法。最后,进行数值模拟实验。实验的结果表明范德华力势能函数模型是可行的,同时,和规范遗传算法相比,改进后的遗传算法能够较大幅度提高算法的搜索效率,并且遗传算法在蛋白质结构预测问题上有巨大潜力。     

A suboptimal algorithm for de novo peptide sequencing via tandem mass spectrometry.

Tandem mass spectrometry has emerged to be one of the most powerful high-throughput techniques for protein identification. Tandem mass spectrometry selects and fragments peptides of interest into N-terminal ions and C-terminal ions, and it measures the mass/charge ratios of these ions. The de novo peptide sequencing problem is to derive the peptide sequences from given tandem mass spectral data of k ion peaks without searching against protein databases. By transforming the spectral data into a matrix spectrum graph G = (V, E), where |V| = O(k(2)) and |E| = O(k(3)), we give the first polynomial time suboptimal algorithm that finds all the suboptimal solutions (peptides) in O(p|E|) time, where p is the number of solutions. The algorithm has been implemented and tested on experimental data. The program is available at http://hto-c.usc.edu:8000/msms/menu/denovo.htm.     

A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry.

Tandem mass spectrometry fragments a large number of molecules of the same peptide sequence into charged molecules of prefix and suffix peptide subsequences and then measures mass/charge ratios of these ions. The de novo peptide sequencing problem is to reconstruct the peptide sequence from a given tandem mass spectral data of k ions. By implicitly transforming the spectral data into an NC-spectrum graph G (V, E) where /V/ = 2k + 2, we can solve this problem in O(/V//E/) time and O(/V/2) space using dynamic programming. For an ideal noise-free spectrum with only b- and y-ions, we improve the algorithm to O(/V/ + /E/) time and O(/V/) space. Our approach can be further used to discover a modified amino acid in O(/V//E/) time. The algorithms have been implemented and tested on experimental data.     

A self-organizing state-space-model approach for parameter estimation in hodgkin-huxley-type models of single neurons

Traditional approaches to the problem of parameter estimation in biophysical models of neurons and neural networks usually adopt a global search algorithm (for example, an evolutionary algorithm), often in combination with a local search method (such as gradient descent) in order to minimize the value of a cost function, which measures the discrepancy between various features of the available experimental data and model output. In this study, we approach the problem of parameter estimation in conductance-based models of single neurons from a different perspective. By adopting a hidden-dynamical-systems formalism, we expressed parameter estimation as an inference problem in these systems, which can then be tackled using a range of well-established statistical inference methods. The particular method we used was Kitagawa's self-organizing state-space model, which was applied on a number of Hodgkin-Huxley-type models using simulated or actual electrophysiological data. We showed that the algorithm can be used to estimate a large number of parameters, including maximal conductances, reversal potentials, kinetics of ionic currents, measurement and intrinsic noise, based on low-dimensional experimental data and sufficiently informative priors in the form of pre-defined constraints imposed on model parameters. The algorithm remained operational even when very noisy experimental data were used. Importantly, by combining the self-organizing state-space model with an adaptive sampling algorithm akin to the Covariance Matrix Adaptation Evolution Strategy, we achieved a significant reduction in the variance of parameter estimates. The algorithm did not require the explicit formulation of a cost function and it was straightforward to apply on compartmental models and multiple data sets. Overall, the proposed methodology is particularly suitable for resolving high-dimensional inference problems based on noisy electrophysiological data and, therefore, a potentially useful tool in the construction of biophysical neuron models.     

Path matching and graph matching in biological networks.

We develop algorithms for the following path matching and graph matching problems: (i) given a query path p and a graph G, find a path p' that is most similar to p in G; (ii) given a query graph G (0) and a graph G, find a graph G (0)' that is most similar to G (0) in G. In these problems, p and G (0) represent a given substructure of interest to a biologist, and G represents a large network in which the biologist desires to find a related substructure. These algorithms allow the study of common substructures in biological networks in order to understand how these networks evolve both within and between organisms. We reduce the path matching problem to finding a longest weighted path in a directed acyclic graph and show that the problem of finding top k suboptimal paths can be solved in polynomial time. This is in contrast with most previous approaches that used exponential time algorithms to find simple paths which are practical only when the paths are short. We reduce the graph matching problem to finding highest scoring subgraphs in a graph and give an exact algorithm to solve the problem when the query graph G (0) is of moderate size. This eliminates the need for less accurate heuristic or randomized algorithms.We show that our algorithms are able to extract biologically meaningful pathways from protein interaction networks in the DIP database and metabolic networks in the KEGG database. Software programs implementing these techniques (PathMatch and GraphMatch) are available at http://faculty.cs.tamu.edu/shsze/pathmatch and http://faculty.cs.tamu.edu/shsze/graphmatch.     

Parallelization of a local similarity algorithm

The local similarity problem is to determine the similar regionswithin two given sequences. We recently developed a dynamicprogramming algorithm for the local similarity problem thatrequires only space proportional to the sum of the two sequencelengths, whereas earlier methods use space proportional to theproduct of the lengths. In this paper, we describe how to parallelizethe new algorithm and present results of experimental studieson an Intel hypercube. The parallel method provides rapid, high-resolutionalignments for users of our software toolkit for pairwise sequencecomparison, as illustrated here by a comparison of the chloroplastgenomes of tobacco and liverwort.     

Decomposition fluorescence spectra of tryptophan residues in proteins based on log-normal components by a least squares method]

An algorithm of decomposition of protein tryptophan spectra into components was developed. The spectral shape of components is described by a uniparametric log-normal function. Rise of certainty and accuracy of resolution of widely overlapping smooth spectral components (a typical uncorrect reverse problem) was achieved using several regularizing factors: (i) the set of experimental spectra used were measured at several quencher concentrations; (ii) the functional being minimized, along with the root mean square residuals of intensities, the term depending on the obedience to the Stern-Volmer law; (iii) an extra information is used--the number of experimental values greatly exceeds the number of parameters to be estimated. The minimum of functional is determined by a consecutive setting of all possible combinations of component spectral maxima values, which allows to avoid sticking in the local minima of noisy functional. The real experimental noise restricts the decomposition into not more than three components. The decomposition error does not exceed the experimental one. The algorithm functioning is illustrated by resolution of tryptophan fluorescence spectra of papain into one, two, and three components.     

An improved stochastic fractal search algorithm for 3D protein structure prediction

Protein structure prediction (PSP) is a significant area for biological information research, disease treatment, and drug development and so on. In this paper, three-dimensional structures of proteins are predicted based on the known amino acid sequences, and the structure prediction problem is transformed into a typical NP problem by an AB off-lattice model. This work applies a novel improved Stochastic Fractal Search algorithm (ISFS) to solve the problem. The Stochastic Fractal Search algorithm (SFS) is an effective evolutionary algorithm that performs well in exploring the search space but falls into local minimums sometimes. In order to avoid the weakness, Lvy flight and internal feedback information are introduced in ISFS. In the experimental process, simulations are conducted by ISFS algorithm on Fibonacci sequences and real peptide sequences. Experimental results prove that the ISFS performs more efficiently and robust in terms of finding the global minimum and avoiding getting stuck in local minimums.     

An approximation algorithm for haplotype inference by maximum parsimony.

This paper studies haplotype inference by maximum parsimony using population data. We define the optimal haplotype inference (OHI) problem as given a set of genotypes and a set of related haplotypes, find a minimum subset of haplotypes that can resolve all the genotypes. We prove that OHI is NP-hard and can be formulated as an integer quadratic programming (IQP) problem. To solve the IQP problem, we propose an iterative semidefinite programming-based approximation algorithm, (called SDPHapInfer). We show that this algorithm finds a solution within a factor of O(log n) of the optimal solution, where n is the number of genotypes. This algorithm has been implemented and tested on a variety of simulated and biological data. In comparison with three other methods, (1) HAPAR, which was implemented based on the branching and bound algorithm, (2) HAPLOTYPER, which was implemented based on the expectation-maximization algorithm, and (3) PHASE, which combined the Gibbs sampling algorithm with an approximate coalescent prior, the experimental results indicate that SDPHapInfer and HAPLOTYPER have similar error rates. In addition, the results generated by PHASE have lower error rates on some data but higher error rates on others. The error rates of HAPAR are higher than the others on biological data. In terms of efficiency, SDPHapInfer, HAPLOTYPER, and PHASE output a solution in a stable and consistent way, and they run much faster than HAPAR when the number of genotypes becomes large.     

Photoacoustic diagnostics of fast photochemical and photobiological processes. Analysis of inverse problem solution

Photoacoustic (PA) diagnostics is a time-resolved experimental technique that measures transient photoinduced volume changes on the nano- and microsecond time-scales. The technique has been used to study the energetics and dynamics of chemical and biochemical reactions initiated by absorption of light. The dynamics of the volume changes and associated relaxation processes can be restored from PA-waveforms by solving an ill-posed problem of deconvolution. For the systems with known relaxation kinetics scheme this problem is usually solved by an iterative approximation algorithm. In complex photoactive systems (e.g. photosynthetic samples), where information about kinetics of fast photoinduced volume changes is not available, an algorithm of direct deconvolution must be used. The implementation of one of the linear deconvolution algorithms (Tikhonov's alpha-regularization) for the PA-diagnostics is therefore considered. The problem of the optimal choice of experimental set-up, and restoration algorithm is analyzed by a numerical simulation. It is shown that the quality of PA-diagnostic experiment is mainly determined by a transfer function converting the relaxation spectrum to the spectrum of output electric signal. The analytical expressions to calculate this function (so called PA-filter) are presented. The performance of two widely used schemes of PA-diagnostics are then directly compared. The time-resolution of the PA-diagnostics in analysis of simultaneous bi-exponential decay is evaluated, and the relationship between the resolving power and parameters of the experimental set-up (signal-to-noise ratio, sampling rate, shape of the PA-filter) is found. The advantage of front face irradiation scheme with piezopolymer film detector for time-resolved measurements is demonstrated.     

An algorithm combining discrete and continuous methods for optical mapping.

Optical mapping is a novel technique for generating the restriction map of a DNA molecule by observing many single, partially digested copies of it, using fluorescence microscopy. The real-life problem is complicated by numerous factors: false positive and false negative cut observations, inaccurate location measurements, unknown orientations, and faulty molecules. We present an algorithm for solving the real-life problem. The algorithm combines continuous optimization and combinatorial algorithms applied to a nonuniform discretization of the data. We present encouraging results on real experimental data and on simulated data.     

Efficient user-channel pairing with power-domain sum-rate maximization in opportunistic hybrid OFDMA-NOMA IoT systems

Non-orthogonal multiple access (NOMA) along with cognitive radio (CR) have been recently configured as potential solutions to fulfill the extraordinary demands of the fifth generation (5G) and beyond (B5G) networks and support the Internet of Thing (IoT) applications. Multiple users can be served within the same orthogonal domains in NOMA via power-domain multiplexing, whilst CR allows secondary users (SUs) to access the licensed spectrum frequency. This work investigates the possibility of combining orthogonal frequency division multiple access (OFDMA), NOMA, and CR, referred to as hybrid OFDMA-NOMA CR network. With this hybrid technology, the licensed frequency is divided into several channels, such as a group SUs is served in each channel based on NOMA technology. In particular, a rate-maximization framework is developed, at which user pairing at each channel, power allocations for each user, and secondary users activities are jointly considered to maximize the sum-rate of the hybrid OFDMA-NOMA CR network, while maintaining a set of relevant NOMA and CR constraints. The developed sum-rate maximization framework is NP-hard problem, and cannot be solved through classical approaches. Accordingly, we propose a two-stage approach; in the first stage, we propose a novel user pairing algorithm. With this, an iterative algorithm based on the sequential convex approximation is proposed to evaluate the solution of the non-convex rate-maximization problem, in the second stage. Results show that our proposed algorithm outperforms the existing schemes, and CR network features play a major role in deciding the overall network’s performance.

     

An approximate matching algorithm for finding (sub-)optimal sequences in S-attributed grammars

MOTIVATION: S-attributed grammars (a generalization of classical Context-Free grammars) provide a versatile formalism for sequence analysis which allows to express long range constraints: the RNA folding problem is a typical example of application. Efficient algorithms have been developed to solve problems expressed with these tools, which generally compute the optimal attribute of the sequence w.r.t. the grammar. However, it is often more meaningful and/or interesting from the biological point of view to consider almost optimal attributes as well as approximate sequences; we thus need more flexible and powerful algorithms able to perform these generalized analyses. RESULTS: In this paper we present a basic algorithm which, given a grammar G and a sequence omega, computes the optimal attribute for all (approximate) strings omega(') in L(G) such that d(omega, omega(')) < or = M, and whose complexity is O(n(r + 1)) in time and O(n(2)) in space (r is the maximal length of the right-hand side of any production of G). We will also give some extensions and possible improvements of this algorithm.     

Protein multiple sequence alignment by hybrid bio-inspired algorithms

This article presents an immune inspired algorithm to tackle the Multiple Sequence Alignment (MSA) problem. MSA is one of the most important tasks in biological sequence analysis. Although this paper focuses on protein alignments, most of the discussion and methodology may also be applied to DNA alignments. The problem of finding the multiple alignment was investigated in the study by Bonizzoni and Vedova and Wang and Jiang, and proved to be a NP-hard (non-deterministic polynomial-time hard) problem. The presented algorithm, called Immunological Multiple Sequence Alignment Algorithm (IMSA), incorporates two new strategies to create the initial population and specific ad hoc mutation operators. It is based on the 'weighted sum of pairs' as objective function, to evaluate a given candidate alignment. IMSA was tested using both classical benchmarks of BAliBASE (versions 1.0, 2.0 and 3.0), and experimental results indicate that it is comparable with state-of-the-art multiple alignment algorithms, in terms of quality of alignments, weighted Sums-of-Pairs (SP) and Column Score (CS) values. The main novelty of IMSA is its ability to generate more than a single suboptimal alignment, for every MSA instance; this behaviour is due to the stochastic nature of the algorithm and of the populations evolved during the convergence process. This feature will help the decision maker to assess and select a biologically relevant multiple sequence alignment. Finally, the designed algorithm can be used as a local search procedure to properly explore promising alignments of the search space.     

Multi-way clustering of microarray data using probabilistic sparse matrix factorization

MOTIVATION: We address the problem of multi-way clustering of microarray data using a generative model. Our algorithm, probabilistic sparse matrix factorization (PSMF), is a probabilistic extension of a previous hard-decision algorithm for this problem. PSMF allows for varying levels of sensor noise in the data, uncertainty in the hidden prototypes used to explain the data and uncertainty as to the prototypes selected to explain each data vector. RESULTS: We present experimental results demonstrating that our method can better recover functionally-relevant clusterings in mRNA expression data than standard clustering techniques, including hierarchical agglomerative clustering, and we show that by computing probabilities instead of point estimates, our method avoids converging to poor solutions.     

Constructing logical models of gene regulatory networks by integrating transcription factor-DNA interactions with expression data: an entropy-based approach

Models of gene regulatory networks (GRNs) attempt to explain the complex processes that determine cells' behavior, such as differentiation, metabolism, and the cell cycle. The advent of high-throughput data generation technologies has allowed researchers to fit theoretical models to experimental data on gene-expression profiles. GRNs are often represented using logical models. These models require that real-valued measurements be converted to discrete levels, such as on/off, but the discretization often introduces inconsistencies into the data. Dimitrova et al. posed the problem of efficiently finding a parsimonious resolution of the introduced inconsistencies. We show that reconstruction of a logical GRN that minimizes the errors is NP-complete, so that an efficient exact algorithm for the problem is not likely to exist. We present a probabilistic formulation of the problem that circumvents discretization of expression data. We phrase the problem of error reduction as a minimum entropy problem, develop a heuristic algorithm for it, and evaluate its performance on mouse embryonic stem cell data. The constructed model displays high consistency with prior biological knowledge. Despite the oversimplification of a discrete model, we show that it is superior to raw experimental measurements and demonstrates a highly significant level of identical regulatory logic among co-regulated genes. A software implementing the method is freely available at: http://acgt.cs.tau.ac.il/modent.     

Computing the reversal distance between genomes in the presence of multi-gene families via binary integer programming

Hannenhalli and Pevzner developed the first polynomial-time algorithm for the combinatorial problem of sorting signed genomic data. Their algorithm determines the minimum number of reversals required for rearranging a genome to another -but only in the absence of gene duplicates. However, duplicates often account for 40% of a genome. In this paper, we show how to extend Hannenhalli and Pevzner's approach to deal with genomes with multi-gene families. We propose a new heuristic algorithm to compute the nearest reversal distance between two genomes with multi-gene families via binary integer programming. The experimental results on both synthetic and real biological data demonstrate that the proposed algorithm is able to find the reversal distance with high accuracy.     

Optimal experimental design for sampling voltage on dendritic trees in the low-SNR regime

Due to the limitations of current voltage sensing techniques, optimal filtering of noisy, undersampled voltage signals on dendritic trees is a key problem in computational cellular neuroscience. These limitations lead to voltage data that is incomplete (in the sense of only capturing a small portion of the full spatiotemporal signal) and often highly noisy. In this paper we use a Kalman filtering framework to develop optimal experimental design methods for voltage sampling. Our approach is to use a simple greedy algorithm with lazy evaluation to minimize the expected square error of the estimated spatiotemporal voltage signal. We take advantage of some particular features of the dendritic filtering problem to efficiently calculate the Kalman estimator’s covariance. We test our framework with simulations of real dendritic branching structures and compare the quality of both time-invariant and time-varying sampling schemes. While the benefit of using the experimental design methods was modest in the time-invariant case, improvements of 25–100% over more na?ve methods were found when the observation locations were allowed to change with time. We also present a heuristic approximation to the greedy algorithm that is an order of magnitude faster while still providing comparable results.