Home > Papers

 
 
The Algorithm for the Special Case of Two-sided SF-MNSA Problem
LIU Nan,ZHU Da-Ming *
School of Computer Science and Technology, Shandong University, Jinan 250101
*Correspondence author
#Submitted by
Subject:
Funding: 教育部高等学校博士学科点专项科研基金（No.20090131110009）, 国家科学自然基金 （No.61070019）, 中国博士后科学基金（No.2011M501133）
Opened online:23 January 2013
Accepted by: none
Citation: LIU Nan,ZHU Da-Ming.The Algorithm for the Special Case of Two-sided SF-MNSA Problem[OL]. [23 January 2013] http://en.paper.edu.cn/en_releasepaper/content/4512994
 
 
Scaffold filling is a new combinatorial optimization problem in genome sequencing and can improve the integrity of the sequencing results.The two-sided Scaffold Filling to Maximize the Number of String Adjacencies(SF-MNSA) problem can be described as: given two incomplete gene sequences $A$ and $B$, respectively fill the missing genes into $A$ and $B$ such that the number of adjacencies between the resulting sequences $A'$ and $B'$ is maximized.The two-sided scaffold filling problem is NP-complete for genomes with duplicated genes and there is no effective approximation algorithm.In this paper, a new version problem is proposed that symbol # is added to each endpoint of each input sequence for any instance of two-sided SF-MNSA problem and a polynomial algorithm for the special instance of this new version problem is designed and proved.
Keywords:Software and Theory; Scaffold Filling; String Adjacency; Breakpoint
 
 
 

For this paper
  • ● PDF (0B)
  • ● Revision 0 　　
  • ● Print this paper
  • ● Recommend this paper to a friend
  • ● Add to my favorite list

    Saved Papers

    Please enter a name for this paper to be shown in your personalized Saved Papers list

Tags
Add yours

Related Papers

Statistics
PDF Downloaded 250
Bookmarked 0
Recommend 5
Comments Array
Submit your papers