【摘要】 探讨了生物信息挖掘中ó模式子序列问题的一个特例,即最长递增子序列(LIS)问题。对于LIS问题,分别用LCS算法、动态规划、动态规划结合二分法进行求解,并分析了这三种算法的时间和空间复杂度,对其中两种算法进行了实现,验证了时间和空间复杂性理论分析的正确性,最后得出了一种高效的LIS算法。更多还原

【Abstract】 This paper introduced a special problem of ó pattern subsequence in bioinformatics mining,that was LIS problem.This paper gave three algorithms of the LIS problem,they were LCS-based,dynamic programming,dynamic programming binary search,and analyzed the advantage and disadvantage of the three algorithms,and tested the performance of the three algorithms’ complexity through experiment.Finally,it educed an effective LIS algorithm.更多还原