[1]柳 楠*,朱永琦,李胜华,等.基于 Contig 的单面基因组片段填充问题研究[J].计算机技术与发展,2022,32(11):8-15.[doi:10. 3969 / j. issn. 1673-629X. 2022. 11. 002]
　LIU Nan*,ZHU Yong-qi,LI Sheng-hua,et al.Research Progress of One-sided Repetitive Genome Scaffold Filling Based on Contig[J].,2022,32(11):8-15.[doi:10. 3969 / j. issn. 1673-629X. 2022. 11. 002]
点击复制

基于 Contig 的单面基因组片段填充问题研究()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
32
期数:
2022年11期
页码:
8-15
栏目:
综述
出版日期:
2022-11-10

文章信息/Info

Title:
Research Progress of One-sided Repetitive Genome Scaffold Filling Based on Contig
文章编号:
1673-629X(2022)11-0008-08
作者:
柳 楠* ; 朱永琦; 李胜华; 崔晓宇
山东建筑大学 计算机科学与技术学院,山东 济南 250101
Author(s):
LIU Nan* ; ZHU Yong-qi; LI Sheng-hua; CUI Xiao-yu
School of Computer Science and Technology,Shandong Jianzhu University,Jinan 250101,China
关键词:
计算生物学; 基因组; 片段填充; 近似算法; NP-完全
Keywords:
computational biology; genome; scaffold filling; approximation algorithms; NP-complete
分类号:
TP301
DOI:
10. 3969 / j. issn. 1673-629X. 2022. 11. 002
摘要:
近些年来,随着基因测序技术的继续发展与应用,大量不完整基因组片段的处理问题有待研究。 同时由于目前大部分的生物学研究是基于基因组序列可以提供完整信息的假设,但通过生物测序技术获得一个完整的基因组序列仍是困难的。 因此基因组重组问题在计算生物学领域愈发受到关注和研究,研究如何填充缺失基因组使其完整,具有重要意义。针对单面基因组片段填充算法,目前常采用最大化公共邻接数目的度量依据,是将缺失基因填充至不完整基因序列中得到填充后的重排列基因序列,使之与参照基因序列之间的新公共邻接数目最大。 主要研究了基于 contig( 片段重叠群) 的单面重复基因组填充问题,重点对该问题的现有算法在近似比、核心技术以及时间复杂度等多方面进行了对比分析与总结,并分别提出了各类算法的改进思路,有助于进一步研究基于 contig 的单面序列填充问题。
Abstract:
In recent years,with the continuous development and application of gene sequencing technology, the number of incompletegenome scaffolds needs to be studied. At the same time,most of the current biological research is based on the assumption that genomesequences can provide complete information, but it is still difficult to obtain a complete genome sequence by biological sequencingtechnology. Therefore,genome recombination has attracted more and more attention and research in the field of computational biology. Itis of great significance to study how to fill the missing genome and make it complete. The one-sided genome scaffold filling algorithm isto fill the missing genes into the incomplete genome scaffold to obtain the filled rearranged genome scaffold,and maximizes the numberof common adjacencies between it and the reference genome scaffold. We mainly study the one-sided repeated genome scaffold fillingproblem based on contig,analyze and summarize the existing algorithms and their time complexity. We focus on the comparative analysisand summary of the existing algorithms in approximation ratio,core technology and time complexity,and put forward the improvementideas of various algorithms,which is helpful for the further study of one-sided scaffold filling problem based on contig in the future.

相似文献/References:

[1]郑锐,刘久富,杨忠,等.马氏田口施密特度量学习算法研究[J].计算机技术与发展,2019,29(04):29.[doi:10. 3969 / j. issn. 1673-629X. 2019. 04. 006]
　ZHENG Rui,LIU Jiu-fu,YANG Zhong,et al.Research on Mahalanobis-Taguchi-Gram-Schmidt Metric Learning Algorithm[J].,2019,29(11):29.[doi:10. 3969 / j. issn. 1673-629X. 2019. 04. 006]
[2]柳 楠*,李胜华,朱永琦.基于 Contig 的双面基因组片段填充算法研究[J].计算机技术与发展,2022,32(12):213.[doi:10. 3969 / j. issn. 1673-629X. 2022. 12. 032]
　LIU Nan*,LI Sheng-hua,ZHU Yong-qi.Research on Two-sided Genome Scaffold Filling Algorithm Based on Contig[J].,2022,32(11):213.[doi:10. 3969 / j. issn. 1673-629X. 2022. 12. 032]
[3]柳 楠,卞忠勇,李 洋,等.基于 Contig 的单面基因组框架填充 2-近似算法[J].计算机技术与发展,2024,34(02):148.[doi:10. 3969 / j. issn. 1673-629X. 2024. 02. 022]
　LIU Nan,BIAN Zhong-yong,LI Yang,et al.A 2-Approximation Algorithm for Contig-based One-sided Genome Scaffold Filling[J].,2024,34(11):148.[doi:10. 3969 / j. issn. 1673-629X. 2024. 02. 022]

更新日期/Last Update: 2022-11-10