上海生物信息学专业高级职称评审政策发表什么期刊
上海生物信息学专业高级职称评审政策发表什么期刊
1.助理职称：（满足以下条件之一）
（1）大学本科毕业，从事专业技术工作一年以上。
（2）大学专科毕业，从事专业技术工作二年以上。
（3）中专毕业，从事专业技术工作三年以上。
（4）高中毕业，从事专业技术工作七年以上。
（5）初中以下学历人员，从事专业技术工作十年以上，同时应具备员级职务。
2.中级职称：（满足以下条件之一）
（1）大学本科毕业，从事专业技术工作五年以上，担任助理职务四年以上。
（2）大学专科毕业，从事专业技术工作六年以上，担任助理职务四年以上。
（3）中专（高中）毕业，从事专业技术工作十年以上，担任助理职务四年以上。
（4）初中以下学历人员须从事专业技术工作十五年以上，担任助理职务四年以上。
3.高级职称：（满足以下条件之一）
（1）大学本科毕业，从事专业工作十年以上，担任中级职务五年以上。
（2）大学专科毕业，从事专业技术工作十五年以上，并担任中级职务五年以上。
（3）中专、高中毕业，从事专业技术工作二十年以上，并担任中级职务五年以上。
4.副高职称：（满足以下条件之一）
博士研究生毕业，取得中级职称，从事专业技术工作两年以上；
硕士研究生毕业，取得中级职称，从事专业技术工作四年以上；
大学本科毕业，取得中级职称，从事专业技术工作五年以上；
大学专科毕业，取得中级职称，从事专业技术工作六年以上。
浅析生物信息学动态规划算法
摘要：生物学中大量数据信息促进了生物信息学的发展，序列数据的日益增多对分析处理数据的算法、模型要求越来越高。在生物信息学中，动态规划算法是最为常用的一种方法，也是最基本的优化方法。其目的就是解决多阶段决策问题和对复杂空间进行优化。动态规划在序列比对、基因识别、结构预测生物分子探针优化问题上起着重要的作用。本文对生物信息学中动态规划的6种算法进行了简单分析，并对比各自的优缺点。
关键词：生物信息学；算法；动态规划
中图分类号：Q811.4文献标识码：A文章编号：1671-6035（2013）08-0000-01
动态规划算法解决问题的基本过程是：把问题的全局解分解为局部解，通过顺序递推的方法不断推进，求出各个局部的最优解，随着局部最优解的不断执行，逐步接近全局的解，最终获得全局最优解。文中比较了6种算法StandardDPA、LazyDPA、Ukkonen'sAlgorithm、Hirschberg、LinearDPA、UkkonenLinear的区别，并比较各自优劣之处。
一、StandardDPA（标准动态规划算法）
StandardDPA是生物信息学中最流行的解决方法，其解决比对问题的基本思想可简述为：使用迭代方法计算出两个序列的相似分值，存于一个得分矩阵中；根据这个得分矩阵，回溯寻找最优的比对序列。标准动态规划算法求解过程是从两个比对序列前端开始，逐步推进，直到两个序列的末端。动态规划算法过程：
•计算过程从d0,0开始，匹配=0，不匹配或者插入/删除=1。每个单元的矩阵，为d[i][j]。
•可以按行计算，每行从左到右，也可以是按列计算，每列从上到下。只要满足在计算di,j
di-1,j、di-1,j-1、和di,j-1都已经被计算这个条件即可。
•在计算di,j后，需要保存di,j是从di-1,j、di-1,j-1、或di,j-1中的哪一个推进的，或保存计算的路径，以便于后续处理。
•上述计算过程到dm,n结束。
标准动态规划算法的优点：因其准确性高而得到广泛应用，适用于字符数量不大的序列，易于理解。缺点：时间和空间复杂度为O(n2),而在实际的生物信息处理中,进行比对的生物序列通常有上万个以上的字符,因此标准动态规划方法不是很实用。
二、LazyDPA（懒惰动态规划算法）
LazyDPA是动态规划算法的一个特例，懒惰的评价是在编程中动态规划算法编辑距离问题快速运行的描述，其表达意思是快。LazyDPA的基本思路：从问题的某一个初始解出发逐步逼近给定的目标，以最快的速度求得更好的解，直到到达最后目标，不能继续进行下，算法停止。这其中的每一步，都是得到的一个当前最优解，传递到下一步，从而保证每一步都是选择当前最优的情况，最后得到结果。每步只考虑一个数据，这个数据满足局部最优条件。如果下一个数据与部分最优解连在一起不再是可行解时，就不把这个数据添加到部分解中。
LazyDPA的优点：减少了计算的单元格数量，适用于相似度较高的两条序列比对，减少了时间和空间的复杂度。缺点：对于相似度稍差的两条序列比对，不能保证得到的结果是最佳的。
三、Ukkonen'sAlgorithm（Ukkonen算法）
Ukkonen也是一种实用非常广泛的算法，这种算法是在基本动态规划算法的基础上加以改进，是一种快速比对算法。Ukkonen算法的平均时间复杂度是O(n+d2),空间复杂度为O(d2)。在此,n是序列的长度,d是两条序列的得分值。但是Ukkonen算法的一个必要条件是所有突变值是正整数,匹配值为0。该算法每次对字符串的前缀生成后缀树，然后考虑字符串的下一个字符，同时在所有的后缀加入到上一个阶段，生成新的后缀树。Ukkonen算法中使用替换矩阵U。矩阵元素U〔ab,d〕表示矩阵D中沿着序列As在对角线ab方向上值为d的最大距离值。
Ukkonen'sAlgorithm的优点：与输入内容或者字符串顺序无关，能大大减少空间。缺点：不能显示最优的比对结果
四、Hirschberg（海尔斯伯格算法）
Hirschberg算法一种基本动态规划算法的优化,能够解决基本动态规划算法空间复杂度太大的问题。此算法的空间复杂度为O(m十n),但是时间复杂度是基本动态规划算法的两倍。
Hirschberg算法的基本思想是:在得分矩阵的计算过程中不存储所有元素,只存储得分矩阵的当前行(或列)和前一行(列)。该算法的描述过程为:在矩阵D的中间列(或行)处将Bs序列分割成两部分,从上和下两个方向计算得分矩阵,以寻找在这一列或行上最优路径所经过的点,这个点称为中间点;递归计算由中间点组成的子矩阵;所有的中间点组成的路径就是一条最佳比对路径。找到两个序列S、T最佳比对的中间点，也就是在两序列最佳比对中找到S的第ｎ/2个字符所对应的序列T中的字符，然后将序列S、T比对的问题转化成序列S1…ｎ/2和序列T1…K及序列Sｎ/2+1…m和序列TK+1…m进行比对的问题。在得分矩阵的计算过程中并不存储所有的元素，只是存储得分矩阵的当前行（列）和前一行（列）。
Hirschberg算法的优点：大大减少了计算的空间复杂度，特别是对于长序列比对，容易进行优化。缺点：时间复杂度太大，计算单元格过多。
五、LinearDPA（线性动态规划算法）
LinearDPA动态规划算法加入了线性空位罚分，空位打分使用固定的变异分值和一个线性函数，来标记在空位中的一组插入或删除。能有效的解决变量、约束条件较多时的问题。这种算法是复杂度为O(n2)的线性间隙成本。
LinearDPA的优点：能有效的解决变量、约束条件较多时的问题。缺点：时间复杂度和空间复杂度都很大。
六、UkkonenLinear
UkkonenLinear算法是Ukkonen算法和LinearDPA的相互补充结合，在线性空间上，运用Ukkonen算法比对序列。开始用Ukkonen算法通过U矩阵进行计算，然后在用基本DPA方法，位于优化比对上的一个矩阵单元允许矩阵分成更小的两个区间，最后在这些更小的区间上进行回溯直到完全的优化比对确定出来。
UkkonenLinear的优点：计算效率高。缺点：适用范围小。
参考文献
[1]生物信息学中的序列比对算法研究[中国农业大学博士论文].唐玉荣。
[2]生物信息学中序列比对算法研究[J].唐玉荣。
[3]两序列比对的Hirschberg算法[J].张福祥。
[4]Lazydynamic-programmingcanbeeagerL[J].Allison。
[5]生物信息学基础[M]。
[6]结构生物信息学[M]。
