in 2001 , the human genome project ( hgp ) consortium and celera genomics reported the first drafts of sequences of the human genome [ 1 , 2 ] . the hgp consortium used the hierarchical sequencing or  clone - by - clone  approach , whereas celera genomics used the whole genome shotgun ( wgs ) approach , which had been successfully used in 1995 to sequence the h. influenzae genome . in the hierarchical sequencing approach , a tiling of large dna sequences , such as bacterial artificial chromosome ( bac ) or yeast artificial chromosome ( yac ) , are constructed for a genome , and each of the sequences is determined .
the hgp consortium used bac as the large sequence , followed by shotgun sequencing of each bac . in sequencing the genome , owing to physical limitations of shotgun sequencing methods
, the genome must be broken down into smaller 
 portions , shotgun reads sized in the range of 600 bps ( base - pairs ) to 800 bps , and as the sequence data for each of these shotgun reads is produced , it must be connecting them 
 with those adjacent and overlapping reads that have been previously sequenced , that is , to achieve an assembly of these smaller sequences into larger contiguous regions or  contigs .  in most cases , the sequences of shotgun reads are obtained by sequencing both ends of a dna fragment whose approximate size is known .
such pair information , referred to as mate - pair information , constrains the placement of the reads within an assembly . in an ideal assembly , all read pairs are placed in such a manner as to satisfy the orientation and distance constraints imposed by the pairing .
mate - pair information can be used to determine the quality of an assembly , because most types of misassemblies lead to violations of these constraints .
in contrast to hierarchical sequencing , wgs breaks a whole genome into small 
 pieces randomly , without shearing into large dna pieces of intermediate size . 

wgs is faster and cheaper than hierarchical sequencing because of the 
 simplicity of the processing steps .
the 
 success of wgs [ 4 , 5 ] has increased its usage and the size of the genome to be sequenced has increased .
although contig assembly programs are well established , less 
 is known about scaffold analysis . while some of its features have been 
 implemented to sequence specific genomes [ 68 ] , the features needed for general scaffold analysis and visualization
consed , a graphical tool for contig 
 assembly , provides good visualization and helps to finish sequencing by 
 connecting with autofinish ; 
 however , it does not have many features related to scaffold analysis .
it has been suggested that the contig scaffolding problem can be solved by greedy - path merging 
 algorithm .
moreover , gigassembler can orient the contigs based on mrna , paired plasmid ends , est , and bac end pairs .
this paper introduces a novel scaffold analysis tool , conpath , which calculates the longest scaffolds . due to the abundance of 
 repeats in genomic dna sequences , a purely overlap - based approach for wgs 
 assembly
is not feasible , but the use of mate - pair information is 
 crucial .
the conpath program uses end read pairs of fixed - sized 
 dna libraries as mate - pairs to calculate orientations , orders , and gap sizes . 

it reads a phrap   output file ( .out ) and an ace format file , which contain contig structures and mate - pair information .
the most important characteristic of conpath is its ability to exploit the mate - pair information of large dna fragments such 
 as fosmids or cosmids , which are about 40 kbps(kilo base - pairs ) in size , or 
 bacs , which are about 100300 kbps in size , rather than plasmids , which are about 
 210 kbps in size .
a mate - pair is composed of two end reads that always face each other .
each end 
 read , 
 b or g , has an orientation relative to the contig containing it .
if the 
 direction of an end read is the same as the direction of the contig , the former 
 has direction 
 u , otherwise , it has direction 
 c. in figure 1 , 
 b has direction 
 u because 
 the cl contig and b read are in the same direction , whereas 
 g has direction c because the c2 contig and g read are in opposite 
 directions .
the size of the mate - pair helps to estimate the gap size between 
 contigs c1 and c2 .  
when one contig contains 
 one end of a mate - pair and a second contig contains the other end of the 
 mate - pair , the two contigs are said to be linked by the mate - pair .
a scaffold 
 is a series of contigs that can be linked by mate - pairs .
the connection relationship of all the contigs can be represented 
 as a graph in which each contig is represented as a vertex .
an edge is created 
 between two contig vertices when they are linked by at least one mate - pair , and 
 the number of linking mate - pairs between two contigs is defined as the edge 
 weight . to construct scaffolds using mate - pair information ,
, cn }   a mate - pair set 
 m = { m1 , m2 , m3 ,  , ml } 
 and a set of reads 
 r = { r1 , r2 , r3 ,  , rs } let g denote the scaffold graph using 
 c and 
 m : 
 ( 1)g=(c , e ) . when a mate - pair 
 mk = ( ri , rj ) 
 exists , in which contig cs contains ri and contig ct contains 
 rj there is an edge between contigs cs and 
 ct .
edge set 
 e is expressed as 
 ( 2)e={ecsct  iff  mk=(ri , rj)  exists for  rics ,  rjct , cs  c , and  ctc}. in constructing 
 a scaffold graph , the linking level 
 ( l ) , the threshold value for the edge weights , was used as a 
 filtering value in constructing and showing scaffolds on output .
when an edge has a weight value smaller than the 
 linking level 
 ( l ) , the edge is 
 discarded from the graph . considering the errors that occur in 
 base calling and contig assembly
, 
 the optimal construction of a scaffold 
 graph is an 
 np - complete problem . to practically solve this problem
, conpath uses a simple greedy algorithm . whenever 
 a new edge is added to the graph , graph 

it is worthwhile noting that conpath determines the relative orientations of all contigs using the orientations of the end reads .
figure 2 shows the determination of the order and orientations of three contigs using two mate - pairs . in figure 2(a ) , 
 b1 and 
 g1 reads 
 determine the relative orientation of contigs 
 c1 and 
 c2 , 
 and , in the same way , 
 b2 and 
 g2 reads 
 determine the relative orientations of contigs 
 c2 and 
 c3 ( see figure 2(b ) ) .
the relative orientations of contigs 
 c1 , c2 , and 
 c3 are determined by rotating the scaffold in figure 2(b ) , as shown in figure 2(c ) . assuming all mate - pairs have a fixed size , the size of the gap between 
 two adjacent contigs is determined 
 by the sizes of the two contigs and the positions 
 of the end reads of contigs .
suppose that contig 
 c1 
  contains 
 b read and contig 
 c2 contains g read .
let gap 
 ( c1 , c2 ) be the gap size between 
 c1 and 
 c2 .
let 
 ps(b ) and 
 pe(b ) be the start and end 
 positions of 
 b read in 
 c1 , respectively , and let 
 ps(g ) and 
 pe(g ) be the start and end 
 positions of 
 g read in 
 c2 , respectively .
considering all the 
 possible directions of a mate - pair 
 of two end reads , conpath estimates 
 the gap size as 
 b - u and g - u : 
 gap ( c1 , c2 ) = matepair size  { ( c1  length  ps(b ) ) + ( c2  length  ps(g ) ) }  
 b - u and g - c : 
 gap ( c1 , c2 ) = matepair size   
 { ( c1  length  ps(b ) ) + pe(g ) ) }  
 b - c and g - u : 
 gap 
 ( c1 ,
c2 ) = matepair size   
 { ( pe(b ) +   ( c2  length  ps(g))}b - c and g - c : 
 gap 
 ( c1 , c2 ) = matepair size  { pe(b ) + pe(g ) } 
  gap ( c1 , c2 ) = matepair size  { ( c1  length  ps(b ) ) + ( c2  length  ps(g ) ) }  
  gap ( c1 , c2 ) = matepair size   
 { ( c1  length  ps(b ) ) + pe(g ) ) }  
  gap 
 ( c1 , c2 ) = matepair size   
 { ( pe(b ) +   ( c2  length  ps(g ) ) } gap 
 ( c1 , c2 ) = matepair size  { pe(b ) + pe(g ) } figure 3 shows the procedure for estimating 
 the gap size between contigs when 
 b and 
 g have 
 u and 
 c directions , respectively .
the orientations of contigs 
 c1 and 
 c2 are set in the same direction .
the length of part of the mate - pair library 
 in contig 
 c1(c1  length  ps(b ) ) 
 and the length of part of the mate - pair 
 library in contig 
 c2(pe(g ) ) are calculated . 
 finally , the gap size is calculated as 
 ( 3)matepair  size  {(c1lengthps(b))+pe(g)}. one important feature of conpath is the verification of a contig assembly by identifying erroneous contigs .
we have defined 4 types 
 of contig assembly errors to check the quality of a contig assembly . 

self - collision errorwhen the number of mate - pairs connecting 
 two adjacent contigs is more than 2 , 
 and there is an inconsistency in determining the orientation of contigs with 
 mate - pairs , the error is defined as a self - collision error , the most serious error type .
if this error occurs , the contigs should be inspected 
 manually one by one . when the number of mate - pairs connecting 
 two adjacent contigs is more than 2 , 
 and there is an inconsistency in determining the orientation of contigs with 
 mate - pairs , the error is defined as a self - collision error , the most serious error type .
if this error occurs , the contigs should be inspected 
 manually one by one .
when a mate - pair of an end read is contained in a contig , the real size of this mate - pair can be calculated .
if the difference between the calculated 
 and predefined sizes is larger than a threshold value , the error is defined as a mate - pair size error .
if the gap size between two contigs is a negative value , it indicates that the two contigs should be merged in the contig assembly process ; this is defined as a gap size error . after calculating the distances of all adjacent contigs
, any two nonadjacent contigs can be overlapped due to the accumulation of errors in gap size estimations .
this type of error is defined as an overlap error , which happens rarely and is not so critical .
identifying error types is useful in verifying and correcting the final result of a contig assembly .
if a contig has more than two types of errors , it is highly probable that a misassembled contig is present .
conpath assigns different colors to contigs by the number of error types , with nonerroneous contigs colored blue .
when one contig has more than one error , conpath assigns this contig a reddish color , with the intensity proportional to the number of error types .
therefore , we can check the quality of the final result of a contig assembly by simply inspecting the color information in the scaffold visualization window of conpath .  
it 
 provides a user - friendly interface and shows visual and color - informative outputs , which can help analyze scaffolds both intuitively and informatively .
conpath provides dialogue windows for  mate - pair information  ,  edge information  ,  contig 
 path  , and  invalid contigs  by automatically checking for the 4 types of 
 errors .
scaffolds are displayed 
 graphically in proportion to the real sizes of vertices and edges after 
 aligning vertices and edges to avoid graphical collision , and the detailed 
 information for each vertex and 
 edge is shown on a pop - up window .
conpath can produce a large picture for 
 all scaffolds by assembling separately printed module pictures .
artificial data were generated in two different versions : r ( randomly ) and 
 u ( uniformly ) .
the 
 r version consisted of contigs of random sizes , whereas the 
 u version consisted of contigs of uniform size . in these artificial data experiments ,
conpath showed very successful scaffold constructions using mate - pair information . from experiments with artificial data ,
conpath worked very successfully and 
 efficiently on real data sets , in sequencing the mannheimia 
 succiniciproducens and vibro vulnificus genomes .
four datasets were tested in sequencing 
 the m. succiniciproducens genome , whereas 
 one dataset was tested in sequencing the v. 
 vulnificus genome , to verify the results of contig assembly .
mh1 , mh2 , mh3   and mh4 are the contig assembly 
 results of the m. succiniciproducens genome 
 and vv is the contig assembly result for 
 the v. vulnificus genome . for the m.
succiniciproducens genome , going from 
 mh1 to mh4 increased the reliability of the contig assembly results .
conpath was most successful at 
 linking level 2 by minimizing the loss of edges .
table 3 
 shows the detected errors in scaffold construction for the 5 datasets . among the m. succiniciproducens datasets , mh1 had the most errors , whereas mh4 had no erroneous contigs .
these results show that identifying the 4 types of errors for contigs is effective in verifying the 
 result of contig assembly .
figure 6 shows the constructed scaffolds at linking levels 2 and 3 for the 
 mh1 dataset .
contig 93 is suspected of being erroneous because it has several erroneous contigs on both sides .
table 4 shows a comparison of features of 
 several scaffold analysis tools , including conpath , consed , autofinish , and bambus .
most importantly , conpath helps users to intuitively verify the contig assembly by providing many visualization features and additional information to detect 
 erroneous contigs .
a scaffold analyzer is a very important tool in genome 
 sequencing , in that it can verify the results of contig assembly and to 
 identify misassembled contigs .
we have developed conpath , a scaffold analyzer that exploits mate - pair information to 
 construct scaffolds by ordering and orienting separate sequence contigs .
conpath provides various useful viewers 
 and dialogue boxes for intuitive understanding . using end read pairs of a fixed - sized mate - pair library
, conpath can determine the relative orientations of all contigs successfully , and estimate the gap size of each adjacent contig pair .
conpath was used successfully in sequencing several microbial 
 genomes , including the m. succiniciproducens genome .
conpath is , therefore , a 
 useful scaffold analyzer to verify contig assembly by detecting erroneous 
 contigs .  
conpath will doubtless improve as its algorithm becomes more 
 correct and efficient , as well as through the development of additional features , 
 such as primer design for the finishing step and a sequence read viewer .
 we have developed a windows - based program , conpath , 
		 as a scaffold analyzer . 
 conpath constructs scaffolds by ordering and orienting separate sequence contigs by exploiting the mate - pair information between 
		  contig - pairs . 
 our algorithm builds directed graphs from link information and traverses them to find the longest acyclic graphs . using end read pairs of fixed - sized mate - pair libraries , 
 conpath determines relative orientations of all contigs , 
 estimates the gap size of each adjacent contig pair , and reports wrong assembly 
 information by validating orientations and gap sizes . 
 we have utilized conpath in more than 10 microbial genome projects , including 
 mannheimia succiniciproducens and vibro vulnificus , 
 where we verified contig assembly and identified several erroneous contigs using the four types of error defined in conpath .   
 also , conpath   supports some convenient features and viewers that permit investigation of each contig in detail ; these include contig viewer , scaffold viewer , edge information list , mate - pair list , and the printing of complex scaffold structures . 
1. INTRODUCTION
2. MATERIALS AND METHODS
3. EXPERIMENTS AND DISCISSION
4. CONCLUSION