讨论翻转距离星树问题，将3SAT问题归约到目标序列部分固定的翻转距离星树问题，证明实例中当有向符号序列个数为3时。若目标序列符号顺序固定，且有部分符号方向给定，则只确定其余符号方向以使得目标序列与已知3条给定序列翻转距离之和最小所对应的翻转距离星树问题也是NP。难解问题。同时，还给出了该问题的多项式时间近似算法。

有向基因组移位排序问题在计算生物学研究中占有重要位置。以前最好的算法时间复杂度为0（n2logn)，该文给出一个有向基因组移位排序的新多项式算法，将移位排序的时间复杂度改进为O（n2）。算法改进的关键在于找到一种寻找有效合理移位的新方法，通过在最小子排列中删除无关顶点确定一个合理移位是否有效，从而将寻找一个有效移位的时间复杂度改进为O（n），总时间复杂度由此降为O（n2）。

本文给聘种求解图最短路径问题的实用反馈式神经网络，并证明这种网络的求解稳定性。这种网络基于最小值选择网而构成，对任意有向图和无向图均能收敛到其唯一的稳定点，由此求得力产所有顶点对间的最短路最短路径长度。本文结果最神经网求解NP-难解类优化问题的一种新尝试。

该交给出基因组Translocation排序问题的一个改进多项式算法，原算法所用存储空间为O（n），时间复杂度为O（n2），文中改进算法仍采用O（n）存储空间，时间复杂度为O（n2logn）具体地，将计算Tranalocation距离的时间复杂度由O（n3）改进为O（n2）， 将计算Translocation序列的时间复杂度由O（n1）改进为O（ntlogn）

讨论基于基因组翻转距离的星型进化树问题的算法和复杂性。首先证明星树问题是NP-难解的，再证明该问题不存在绝对近似求解算法，最后给出一个求解星树问题的常数近似算法，近似性能比为2。

提出一种一般二进制映射问题的前馈网络学习算法，给出一种求解超平面以几何分割练点的新方法，不仅相应地构造了陷层神经网络，而且使得只需再构造一个输出层网络便可实现训练样本所描述的映射，该算法在学习收敛速度方面优于BP算法和SC算法，对样本数据的分布和密集程度变化适应性强，具有较好的容错能力。

分类问题在前向神经网络研究中占有重要集团，本文利用几何方法给耻骨一个二进制神经网络K（≥2）分类问题的新学习算法。算法通过训练点的几休位置与类别分析，建立一个四层前向神经网络，实现网络四舍五入向量分类。 本文算法的优点在于：保证学习收敛且收敛速度快于BP算法及已有的其他一些前向网络学习算法；算法可以确定神经网络的结且能实现精确有向量分类。另外，算法所建神网络由线性阀值单元组成，神经元突触权值和阀值均为整数，特别适合于集成电路实现。

Binary de bruijin sequences have been widely used and studied. In this paper: two new algorithms for producing binary de bruijing sequences are presented. The first algorithm is acquired by improving the original algorithm proposed by Yuejiang Fluang. It takes An bits of storage and 2n units of time to produce one bit of sequence, witere the space complexity is identical to that of Hnang's algorithm. and the time complexity is one half that of Huang's algorithm. The sceond algorithm cmploys a new method to produce binary de bruijin sequences. It takes An bits of storage and n units of time to produce one bit, where the time complexity is one quarter that of Huang's aigorithm, THE other advantages of the two new aigorithins are that they produce de bruijin sequences with better 01 harmoniousness and can start computing from any n-tuple.

Genome rearrangement is an important area in computational biology. There are three basic operations, reversal, translocation and transposition. Herewestudy the translocation operations. Multi-chromosomal genomes frequently evolve by translocation events that exchange genetic material between two chromosomes.We focus on the signed case, where the direction of each gene is known. The signed translocation problem asks to find the minimum number of translocation operations as well as the sequence of translocation operations to transform one genome into the other.A linear-time algorithm that computes the minimum number of translocation operations was given in a linear-time algorithm for computing translocation distance between signed genomes [16]. However, that algorithm cannot give the optimum sequence of translocation operations. The best known algorithm that can give the optimum sequence of translocation operations for signed translocation problem runs in O(n2 log n) time. In this paper, we design an O(n2) algorithm.

The research on approximated algorithms for k-Median problem is a focus of computer scientists all along, and most existed results are based on Euclidean and Metric k-Median problem, however, results for General distance space k-Median is not found for many years. In General distance space, let dmax/dmin denote the maximum value of the length of the longest edge divided by the length of the ortest edge for one client point. In this paper, we first prove that there are no polynomial algorithms of approximation ratio 1+e1−ωk-Median with condition dmax/dmin≤ω+ε, unlessDTIMNP⊆result implies there are no polynomial algorithms of approximation ratio 1+2elog (lognone2 for Metric k-Median unless. Then a local search algorithm for k-Median is presented. New analysis shows that local search can achieve a ratio of