Rapid Evaluation of Least-Squares and Minimum-Evolution Criteria on Phylogenetic Trees

We present fast new algorithms for evaluating trees with respectto least squares and minimum evolution (ME), the most commonlyused criteria for inferring phylogenetic trees from distancedata. The new algorithms include an optimal O(N2) time algorithmfor calculating the edge (branch or internode) lengths on atree according to ordinary or unweighted least squares (OLS);an O(N3) time algorithm for edge lengths under weighted leastsquares (WLS) including the Fitch-Margoliash method; and anoptimal O(N4) time algorithm for generalized least-squares (GLS)edge lengths (where N is the number of taxa in the tree). TheME criterion is based on the sum of edge lengths. Consequently,the edge lengths algorithms presented here lead directly toO(N2), O(N3), and O(N4) time algorithms for ME under OLS, WLS,and GLS, respectively. All of these algorithms are as fast asor faster than any of those previously published, and the algorithmsfor OLS and GLS are the fastest possible (with respect to orderof computational complexity). A major advantage of our new methodsis that they are as well adapted to multifurcating trees asthey are to binary trees. An optimal algorithm for determiningpath lengths from a tree with given edge lengths is also developed.This leads to an optimal O(N2) algorithm for OLS sums of squaresevaluation and corresponding O(N3) and O(N4) time algorithmsfor WLS and GLS sums of squares, respectively. The GLS algorithmis time-optimal if the covariance matrix is already inverted.The speed of each algorithm is assessed analytically—thespeed increases we calculate are confirmed by the dramatic speedincreases resulting from their implementation in PAUP* 4.0.The new algorithms enable far more extensive tree searches andstatistical evaluations (e.g., bootstrap, parametric bootstrap,or jackknife) in the same amount of time. Hopefully, the fastalgorithms for WLS and GLS will encourage the use of these criteriafor evaluating trees and their edge lengths (e.g., for approximatedivergence time estimates), since they should be more statisticallyefficient than OLS.     

A \sqrt N Dynamic Load Distribution Algorithm Using Anti-Tasks and Load State Vectors

One of the fundamental issues to ensure maximal performance improvement in a cluster computing environment is load distribution, which is commonly achieved by using polling-based load distribution algorithms. Such algorithms suffer from two weaknesses: (1) Load information exchanged during a polling session is confined to the two negotiating nodes only. (2) Such algorithms are not scalable in that growth of the distributed system is accompanied with increasing amount of polling sessions.In this paper, we proposed a LD algorithm which is based on anti-tasks and load state vectors. Anti-tasks travel around the distributed system for pairing up task senders and receivers. As an anti-task travels, timed load information is collected and disseminated over the entire system via the load state vector bundled with the anti-task. Guided by load state vectors, anti-tasks are spontaneously directed towards processing nodes having high transient workload, thus allowing their surplus workload to be relocated soonest possible. No peer-to-peer negotiations between senders and receivers are needed.To reduce the network bandwidth consumption caused by the anti-task algorithm, the number of hosts that an anti-task needs to travel to must be carefully limited. The algorithm achieves this by employing the mathematical notion of Finite Projective Plane (FPP). By employing FPP, the number of nodes that each anti-task has to travel is at most , where N is the number of nodes in the system, without sacrifying the spread of load information.     

Constraints-based genome-scale metabolic simulation for systems metabolic engineering

Random mutagenesis and selection approaches used traditionally for the development of industrial strains have largely been complemented by metabolic engineering, which allows purposeful modification of metabolic and cellular characteristics by using recombinant DNA and other molecular biological techniques. As systems biology advances as a new paradigm of research thanks to the development of genome-scale computational tools and high-throughput experimental technologies including omics, systems metabolic engineering allowing modification of metabolic, regulatory and signaling networks of the cell at the systems-level is becoming possible. In silico genome-scale metabolic model and its simulation play increasingly important role in providing systematic strategies for metabolic engineering. The in silico genome-scale metabolic model is developed using genomic annotation, metabolic reactions, literature information, and experimental data. The advent of in silico genome-scale metabolic model brought about the development of various algorithms to simulate the metabolic status of the cell as a whole. In this paper, we review the algorithms developed for the system-wide simulation and perturbation of cellular metabolism, discuss the characteristics of these algorithms, and suggest future research direction.     

蛋白质结构成对比较的新方法

介绍一种蛋白质三维结构的快速比较方法.此方法毋需初始联配,而能自动寻找和智能迭代.利用本程序对珠蛋白、丝氨酸蛋白酶、天冬氨酸蛋白酶、钙结合蛋白和溶菌酶作了系统的结构比较,取得了满意的结果.本文也讨论了衡量联配结果好坏的要素问题.     

Mapping QTLs and candidate genes for iron and zinc concentrations in unpolished rice of Madhukar×Swarna RILs

Identifying QTLs/genes for iron and zinc in rice grains can help in biofortification programs. 168 F(7) RILs derived from Madhukar×Swarna were used to map QTLs for iron and zinc concentrations in unpolished rice grains. Iron ranged from 0.2 to 224ppm and zinc ranged from 0.4 to 104ppm. Genome wide mapping using 101 SSRs and 9 gene specific markers showed 5 QTLs on chromosomes 1, 3, 5, 7 and 12 significantly linked to iron, zinc or both. In all, 14 QTLs were identified for these two traits. QTLs for iron were co-located with QTLs for zinc on chromosomes 7 and 12. In all, ten candidate genes known for iron and zinc homeostasis underlie 12 of the 14 QTLs. Another 6 candidate genes were close to QTLs on chromosomes 3, 5 and 7. Thus the high priority candidate genes for high Fe and Zn in seeds are OsYSL1 and OsMTP1 for iron, OsARD2, OsIRT1, OsNAS1, OsNAS2 for zinc and OsNAS3, OsNRAMP1, Heavy metal ion transport and APRT for both iron and zinc together based on our genetic mapping studies as these genes strictly underlie QTLs. Several elite lines with high Fe, high Zn and both were identified.