WinHAP: An Efficient Haplotype Phasing Algorithm Based on Scalable Sliding Windows

Haplotype phasing represents an essential step in studying the association of genomic polymorphisms with complex genetic diseases, and in determining targets for drug designing. In recent years, huge amounts of genotype data are produced from the rapidly evolving high-throughput sequencing technologies, and the data volume challenges the community with more efficient haplotype phasing algorithms, in the senses of both running time and overall accuracy. 2SNP is one of the fastest haplotype phasing algorithms with comparable low error rates with the other algorithms. The most time-consuming step of 2SNP is the construction of a maximum spanning tree (MST) among all the heterozygous SNP pairs. We simplified this step by replacing the MST with the initial haplotypes of adjacent heterozygous SNP pairs. The multi-SNP haplotypes were estimated within a sliding window along the chromosomes. The comparative studies on four different-scale genotype datasets suggest that our algorithm WinHAP outperforms 2SNP and most of the other haplotype phasing algorithms in terms of both running speeds and overall accuracies. To facilitate the WinHAP's application in more practical biological datasets, we released the software for free at: http://staff.ustc.edu.cn/~xuyun/winhap/index.htm.     

Efficient Parallel Levenberg-Marquardt Model Fitting towards Real-Time Automated Parametric Imaging Microscopy

We present a fast, accurate and robust parallel Levenberg-Marquardt minimization optimizer, GPU-LMFit, which is implemented on graphics processing unit for high performance scalable parallel model fitting processing. GPU-LMFit can provide a dramatic speed-up in massive model fitting analyses to enable real-time automated pixel-wise parametric imaging microscopy. We demonstrate the performance of GPU-LMFit for the applications in superresolution localization microscopy and fluorescence lifetime imaging microscopy.     

An Algorithm for Testing the Efficient Market Hypothesis

The objective of this research is to examine the efficiency of EUR/USD market through the application of a trading system. The system uses a genetic algorithm based on technical analysis indicators such as Exponential Moving Average (EMA), Moving Average Convergence Divergence (MACD), Relative Strength Index (RSI) and Filter that gives buying and selling recommendations to investors. The algorithm optimizes the strategies by dynamically searching for parameters that improve profitability in the training period. The best sets of rules are then applied on the testing period. The results show inconsistency in finding a set of trading rules that performs well in both periods. Strategies that achieve very good returns in the training period show difficulty in returning positive results in the testing period, this being consistent with the efficient market hypothesis (EMH).     

Acceleration of cryo-EM Flexible Fitting for Large Biomolecular Systems by Efficient Space Partitioning

1. Download high-res image (287KB)
2. Download full-size image

     

Multimode Optical Fiber Surface Plasmon Resonance Signal Processing Based on the Fourier Series Fitting

Multimode optical fiber is widely used because of its large core size, strong light-gathering ability, and remote on-line sensing ability in various environments. Due to the mode coupling and polarization loss, the signal curve obtained has wide full width at half-maximum (FWHM) and small peak value. Therefore, efficient methods to calculate the resonant wavelength are required. This paper presents a method to process the surface plasmon resonance curve (SPR) based on the Fourier series fitting. The calculated resonant wavelength is obtained with one-dimensional extremum-search method. Experiment results show the proposed method can accurately calculate the resonant wavelength of high concentration solution. Additionally, the method has higher sensitivity and is unaffected by the light source fluctuation. This method has potential value in processing the SPR signal of the multimode optical fiber.     

Efficient Prediction of Co-Complexed Proteins Based on Coevolution

The prediction of the network of protein-protein interactions (PPI) of an organism is crucial for the understanding of biological processes and for the development of new drugs. Machine learning methods have been successfully applied to the prediction of PPI in yeast by the integration of multiple direct and indirect biological data sources. However, experimental data are not available for most organisms. We propose here an ensemble machine learning approach for the prediction of PPI that depends solely on features independent from experimental data. We developed new estimators of the coevolution between proteins and combined them in an ensemble learning procedure.We applied this method to a dataset of known co-complexed proteins in Escherichia coli and compared it to previously published methods. We show that our method allows prediction of PPI with an unprecedented precision of 95.5% for the first 200 sorted pairs of proteins compared to 28.5% on the same dataset with the previous best method.A close inspection of the best predicted pairs allowed us to detect new or recently discovered interactions between chemotactic components, the flagellar apparatus and RNA polymerase complexes in E. coli.     

Chemical Reduction of Phosphate on the Primitive Earth

If phosphorus played a role in the origin of life, some means of concentrating micromolar levels of phosphate (derived from the calcium phosphate mineral apatite), must first have been available. Here we show that simulated (mini)lightning discharges in model prebiotic atmospheres, including only minimally reducing ones, reduce orthophosphates, including apatite, to produce substantial yields of phosphite. Electrical discharges associated with volcanic eruptions could have provided a particularly suitable environment for this process. Production of relatively soluble and reactive phosphite salts could have supplied a pathway by which the first phosphorus atoms were incorporated into (pre)biological systems.     

Generalized Baum-Welch Algorithm Based on the Similarity between Sequences

The profile hidden Markov model (PHMM) is widely used to assign the protein sequences to their respective families. A major limitation of a PHMM is the assumption that given states the observations (amino acids) are independent. To overcome this limitation, the dependency between amino acids in a multiple sequence alignment (MSA) which is the representative of a PHMM can be appended to the PHMM. Due to the fact that with a MSA, the sequences of amino acids are biologically related, the one-by-one dependency between two amino acids can be considered. In other words, based on the MSA, the dependency between an amino acid and its corresponding amino acid located above can be combined with the PHMM. For this purpose, the new emission probability matrix which considers the one-by-one dependencies between amino acids is constructed. The parameters of a PHMM are of two types; transition and emission probabilities which are usually estimated using an EM algorithm called the Baum-Welch algorithm. We have generalized the Baum-Welch algorithm using similarity emission matrix constructed by integrating the new emission probability matrix with the common emission probability matrix. Then, the performance of similarity emission is discussed by applying it to the top twenty protein families in the Pfam database. We show that using the similarity emission in the Baum-Welch algorithm significantly outperforms the common Baum-Welch algorithm in the task of assigning protein sequences to protein families.     

Primitive Auditory Memory Is Correlated with Spatial Unmasking That Is Based on Direct-Reflection Integration

In reverberant rooms with multiple-people talking, spatial separation between speech sources improves recognition of attended speech, even though both the head-shadowing and interaural-interaction unmasking cues are limited by numerous reflections. It is the perceptual integration between the direct wave and its reflections that bridges the direct-reflection temporal gaps and results in the spatial unmasking under reverberant conditions. This study further investigated (1) the temporal dynamic of the direct-reflection-integration-based spatial unmasking as a function of the reflection delay, and (2) whether this temporal dynamic is correlated with the listeners’ auditory ability to temporally retain raw acoustic signals (i.e., the fast decaying primitive auditory memory, PAM). The results showed that recognition of the target speech against the speech-masker background is a descending exponential function of the delay of the simulated target reflection. In addition, the temporal extent of PAM is frequency dependent and markedly longer than that for perceptual fusion. More importantly, the temporal dynamic of the speech-recognition function is significantly correlated with the temporal extent of the PAM of low-frequency raw signals. Thus, we propose that a chain process, which links the earlier-stage PAM with the later-stage correlation computation, perceptual integration, and attention facilitation, plays a role in spatially unmasking target speech under reverberant conditions.     

基于改进的模糊C均值聚类的肺结节计算机辅助诊断算法研究

目的:研究基于改进的模糊C均值聚类计算机辅助诊断算法对肺结节的诊断价值,降低对肺结节的漏诊率,提高病人的生存率.方法:基于模糊C均值聚类的算法,利用直方图统计特性对数据进行优化,在此基础上利用像素的邻域特性,将数据样本对各聚类中心约束条件为1,改变为隶属度之和为样本总数.用改进的FCM对肺实质图像进行分割,将分割后的图像应用区域标记算法去除小面积区域.利用肺结节的关键特征,提取可疑区域.结果:运用改进算法后,区域分割效果更好.仿真结果证明算法很好的将"线"形或分枝状结构的血管去除.结论:改进的FCM有很好的实时性和对噪声的鲁棒性,分离血管后,将可疑区域在原图标记出来,使医生的工作更加明确.     

Efficient All-Optical Molecule-Plasmon Modulation Based on T-shape Single Slit

Efficient all-optical molecule-plasmon modulation is experimentally demonstrated by employing a compact T-shape single slit on a metal film coated with an azopolymer film, in which the azobenzene molecules can be reoriented by a pump beam. In the T-shape single slit, the transmission spectra exhibit periodic behaviors and are quite sensitive to variations of the refractive index of the azopolymer in the groove. Under a pump beam, the azobenzene molecules are reoriented, so the SPPs in the groove feel a refractive index quite different from that of the originally isotropic azopolymer with randomly orientations. This leads to a high modulation depth of about 53 % (3.3 dB) and a phase variation of >π experimentally.     

Reduction and Activation of Phosphate on the Primitive Earth

Electrical discharges in water-saturated N₂ containing 1–10% CH₄ were shown earlier toreduce phosphate to phosphite. This mechanism was suggestedas a possible source of water-soluble phosphorus-containing compounds in volcanic environments on the prebiotic Earth.We have now extended our investigations to gas mixtures inwhich CO₂ and N₂ are the main components, and studied the effect of introducing smallamounts of H₂ and CO.We show that surprisingly high conversions to phosphite occurin reducing mixtures and thatseveral percent reduction of apatite occurs even in thepresence of as little as 1% each of H₂ and CO. We were also able to confirm a previous report ofpolyphosphate production as a result of heating the mineral apatite in the presence of other minerals.     

Multi-Objective Community Detection Based on Memetic Algorithm

Community detection has drawn a lot of attention as it can provide invaluable help in understanding the function and visualizing the structure of networks. Since single objective optimization methods have intrinsic drawbacks to identifying multiple significant community structures, some methods formulate the community detection as multi-objective problems and adopt population-based evolutionary algorithms to obtain multiple community structures. Evolutionary algorithms have strong global search ability, but have difficulty in locating local optima efficiently. In this study, in order to identify multiple significant community structures more effectively, a multi-objective memetic algorithm for community detection is proposed by combining multi-objective evolutionary algorithm with a local search procedure. The local search procedure is designed by addressing three issues. Firstly, nondominated solutions generated by evolutionary operations and solutions in dominant population are set as initial individuals for local search procedure. Then, a new direction vector named as pseudonormal vector is proposed to integrate two objective functions together to form a fitness function. Finally, a network specific local search strategy based on label propagation rule is expanded to search the local optimal solutions efficiently. The extensive experiments on both artificial and real-world networks evaluate the proposed method from three aspects. Firstly, experiments on influence of local search procedure demonstrate that the local search procedure can speed up the convergence to better partitions and make the algorithm more stable. Secondly, comparisons with a set of classic community detection methods illustrate the proposed method can find single partitions effectively. Finally, the method is applied to identify hierarchical structures of networks which are beneficial for analyzing networks in multi-resolution levels.     

基于局部调整动态轮廓模型提取超声图像乳腺肿瘤边缘

提出一种基于局部调整动态轮廓模型提取超声图像乳腺肿瘤边缘的算法。该算法在Chan—Vese（CV）模型基础上,定义了一个局部调整项,采用基于水平集的动态轮廓模型提取超声图像乳腺肿瘤边缘。将该算法应用于89例临床超声图像乳腺肿瘤的边缘提取实验,结果表明：该算法比CV模型更适用于具有区域非同质性的超声图像的分割,可有效实现超声图像乳腺肿瘤边缘的提取。     

An Efficient Supervised Training Algorithm for Multilayer Spiking Neural Networks

The spiking neural networks (SNNs) are the third generation of neural networks and perform remarkably well in cognitive tasks such as pattern recognition. The spike emitting and information processing mechanisms found in biological cognitive systems motivate the application of the hierarchical structure and temporal encoding mechanism in spiking neural networks, which have exhibited strong computational capability. However, the hierarchical structure and temporal encoding approach require neurons to process information serially in space and time respectively, which reduce the training efficiency significantly. For training the hierarchical SNNs, most existing methods are based on the traditional back-propagation algorithm, inheriting its drawbacks of the gradient diffusion and the sensitivity on parameters. To keep the powerful computation capability of the hierarchical structure and temporal encoding mechanism, but to overcome the low efficiency of the existing algorithms, a new training algorithm, the Normalized Spiking Error Back Propagation (NSEBP) is proposed in this paper. In the feedforward calculation, the output spike times are calculated by solving the quadratic function in the spike response model instead of detecting postsynaptic voltage states at all time points in traditional algorithms. Besides, in the feedback weight modification, the computational error is propagated to previous layers by the presynaptic spike jitter instead of the gradient decent rule, which realizes the layer-wised training. Furthermore, our algorithm investigates the mathematical relation between the weight variation and voltage error change, which makes the normalization in the weight modification applicable. Adopting these strategies, our algorithm outperforms the traditional SNN multi-layer algorithms in terms of learning efficiency and parameter sensitivity, that are also demonstrated by the comprehensive experimental results in this paper.     

Efficient Deterministic Finite Automata Minimization Based on Backward Depth Information

Obtaining a minimal automaton is a fundamental issue in the theory and practical implementation of deterministic finite automatons (DFAs). A minimization algorithm is presented in this paper that consists of two main phases. In the first phase, the backward depth information is built, and the state set of the DFA is partitioned into many blocks. In the second phase, the state set is refined using a hash table. The minimization algorithm has a lower time complexity O(n) than a naive comparison of transitions O(n²). Few states need to be refined by the hash table, because most states have been partitioned by the backward depth information in the coarse partition. This method achieves greater generality than previous methods because building the backward depth information is independent of the topological complexity of the DFA. The proposed algorithm can be applied not only to the minimization of acyclic automata or simple cyclic automata, but also to automata with high topological complexity. Overall, the proposal has three advantages: lower time complexity, greater generality, and scalability. A comparison to Hopcroft’s algorithm demonstrates experimentally that the algorithm runs faster than traditional algorithms.     

Efficient Learning Strategy of Chinese Characters Based on Network Approach

We develop an efficient learning strategy of Chinese characters based on the network of the hierarchical structural relations between Chinese characters. A more efficient strategy is that of learning the same number of useful Chinese characters in less effort or time. We construct a node-weighted network of Chinese characters, where character usage frequencies are used as node weights. Using this hierarchical node-weighted network, we propose a new learning method, the distributed node weight (DNW) strategy, which is based on a new measure of nodes'' importance that considers both the weight of the nodes and its location in the network hierarchical structure. Chinese character learning strategies, particularly their learning order, are analyzed as dynamical processes over the network. We compare the efficiency of three theoretical learning methods and two commonly used methods from mainstream Chinese textbooks, one for Chinese elementary school students and the other for students learning Chinese as a second language. We find that the DNW method significantly outperforms the others, implying that the efficiency of current learning methods of major textbooks can be greatly improved.     

基于DNA序列数据挖掘算法研究

引入数据挖掘技术,研究DNA序列数据内在规律性,并给出DNA序列分类问题的算法．综合考虑碱基组的出现概率以及相邻氨基酸之间的关系,从DNA序列片段的个案中密码子分布密度角度出发,提取出已知类别的DNA序列片段的特征;应用分类的逐步判别分析方法,剔除判别能力不显著的变量,给出DNA序列分类的判别函数．仿真结果表明,该算法具有分类计算公式简单且分类结果精度的优点．     

A Tetra-Orthogonal Strategy for the Efficient Synthesis of Scaffolds Based on Cyclic Peptides

We have developed a straightforward and robust strategy for synthesizing a family of cyclic peptide scaffolds for the presentation of defined moieties in a wide range of orientations. Specifically we are exploring quinoxaline as the moiety, as a potential nucleic acid binding motif. The method requires the use of four degrees of orthogonality, which in turn allow the extension of the main chain, incorporation of the target side chains, on-resin cyclization, and the revelation of an amino group upon cleavage to increase solubility. We show that related approaches fail for a range of reasons, including the failure of cyclization. Following the optimization of the approach with a single cyclic peptide, we synthesized a family of all possible bis and tris quinoxaline adducts showing by ESI–MS that the desired full length cyclic product is produced in a majority of cases.