【摘 要】
:
Classical sorting by reversals uses the unit-cost model, that is, each reversal consumes an equal cost. This model limits the biological meaning of sorting by r
【机 构】
:
Department of Mathematics National University of Singapore,School of Computing
【出 处】
:
基因组、蛋白质组与生物信息学报(英文版)
【基金项目】
:
thank anonymous reviewers for their helpful comments
论文部分内容阅读
Classical sorting by reversals uses the unit-cost model, that is, each reversal consumes an equal cost. This model limits the biological meaning of sorting by reversal.Bender and his colleagues extended it by assigning a cost function f(l) = lα for all α≥ 0, where l is the length of the reversed subsequence. In this paper, we extend their results by considering a model in which long reversals are prohibited. Using the same cost function above for permitted reversals, we present tight or nearly tight bounds for the worst-case cost of sorting by reversals. Then we develop algorithms to approximate the optimal cost to sort a given 0/1 sequence as well as a given permutation. Our proposed problems are more biologically meaningful and more algorithmically general and challenging than the problem considered by Bender et al. Furthermore, our bounds are tight and nearly tight, whereas our algorithms provide good approximation ratios compared to the optimal cost to sort 0/1 sequences or permutations by reversals.
其他文献
Wood of Chinese fir and poplar were liquefied in phenol at 150℃ and atmospheric pressure. The liquefied wood were reacted with formaldehyde to synthesize the l
黄酮是植物体内一类重要的次生代谢产物,具有重要的生态作用和经济价值.但目前对兴安落叶松黄酮的研究很少.本论文研究了自然条件下兴安落叶松黄酮动态变化的特征,并对黄酮与
采用RPLC-SDS-PAGE与纳升毛细管液相色谱-串联质谱联用技术对国际人类蛋白质组织(HUPO)提供的法国人肝脏蛋白质组表达谱的构建及其理化性质的统计分析,鉴定了2552条肽段,归结
面对当前日益严峻的生态问题,构建社会主义生态文明是可持续发展观的题中之意.作为社会可持续发展的思想基础和精神支持,生态文明的建设要经历价值观念、生产模式及消费模式
目的 研究吲哚青绿介导光动力疗法治疗兔眼后发性白内障后,兔眼视网膜的损伤情况.方法 32只兔眼随机分为对照组、低剂量组、中剂量组、高剂量组,分别行晶状体超声乳化及皮质
目的 探讨变应性咳嗽(AC)的诊断、治疗及其气道炎症特点.方法 采用的病因诊断程序,对158例慢性咳嗽患者进行病因诊断;结合诱导痰方法,分析痰液中细胞分类,分别采用荧光酶免疫
目的 对反复供精人工授精(AID)失败者进行宫腹腔镜诊疗,并评价子宫输卵管碘油造影(HSG)检测输卵管通畅的灵敏度及特异度.方法 回顾性分析321例因反复AID失败而收住女性科行宫
目的 评估慢性心力衰竭中西医结合临床路径多中心实施的效益.方法 采用非同期历史对照研究与同期临床对照研究相结合的方法,全国4家医院实施临床路径规范化管理后,评估其对患
本文通过对2000-2002年度我国医药卫生学科科技论文的统计与分析,从一个侧面探讨了我国医药卫生科技发展的现状与趋势,阐明了加大科技创新投入、完善学科发展结构、促进科学
In order to analyze the effects of the temperature gradient on moisture movement during the highly intensive microwave-vacuum drying, thermal diffusion of Masso