Open Access


  • Zeev Frenkel1Email author,
  • Etienne Paux2,
  • David Mester1,
  • Catherine Feuillet2 and
  • Abraham Korol1
BMC Bioinformatics201011:584

DOI: 10.1186/1471-2105-11-584

Received: 7 September 2010

Accepted: 30 November 2010

Published: 30 November 2010









Until very recently, genome sequencing projects such as the human ([1, 2]), mouse ([3], rice ([4]), or maize genome projects ([5, 6]) have relied on the construction of physical maps as a framework to support BAC-by-BAC or whole-genome shotgun sequencing [7]. Alternatively, genome sequencing could be conducted via whole genome shotgun approach ([811] etc.) or using the novel next generation sequencing technologies (e.g., [1214]). Physical maps can be established via BAC clones fingerprinting using restriction enzyme profiling [1522] or by digital fingerprinting [2325], and subsequent assembly of the clones into contigs based on the systematic comparison of fingerprint profiles. BAC contigs are then ordered using molecular markers and genetic or radiation hybrid maps. In addition, to providing a framework for sequencing, such maps can be used for high-resolution gene mapping [2628] and map-based gene cloning [2934]. Despite significant progress in fingerprinting techniques such as High Information Content Fingerprinting (HICF) [22] and the development of efficient programs such as FPC (FingerPrinted Contigs) [35, 36], maximal likelihood-based reconstruction of physical map [37, 38], random cost algorithm minimizing triplewise linking distance [39], etc. to automatically cluster clones into contigs, physical mapping remains long, laborious, and expensive especially for large and complex genomes that contain a high amount of repeated sequences (e.g., maize or wheat genome). Therefore, the development of algorithms and methods making this process more cost effective is important in view of the increasing amount of non-model species that will be sequenced in the near future.







I. Contigs Construction


(i) Calculation of p-values for clone overlaps


Let n1 and n2 be the numbers of bands in clones c1 and c2. LTC approximates the probability that the number of bands present in both clones c1 and c2 is equal or higher than k by exp{-(a0 + a1k + a2k2)}, for k > k0. Coefficients a0, a1, and a2 are estimated by the Monte-Carlo method, i.e., by simulating a large number of pairs of random clones (with n1 and n2 bands) and scoring the "observed" number of shared bands (refer to Additional file 1, Section 1 for details); value k0 is defined by inequality: exp{-(a0 + a1k + a2k2)} < 0.001 for all k > k0 (see also Additional file 1, Section 2). Shared genetic markers are taken into account by adding the term amarkm to a0 + a1k + a2k2, where m is the number of shared markers. We used amark = 100 ln 10 to make the overlap of clones with a shared marker more significant than 10-100. If bands are not assumed to be identically abundant, then the number of shared bands k is represented by -∑ lnf b , where the sum is taken over all shared bands and f b is the abundance of band b. Clearly, if all bands have equal abundances then k is proportional to the number of shared bands (i.e., both formulations will give the same result). Values f b can be estimated by the maximum likelihood method: the probability that a random clone with n bands contains band b is 1-(1-f b ) n . [Logarithm of likelihood is then equal to ∑ c with b log(1-(1-f b )n(c)) + ∑ c without b log((1-f b )n(c)); for small f b (f b <<1/nmax, nmax= max c n(c)), the maximum likelihood estimation for f b is close to nmean-1π b /(1-π b ), where π b is a proportion of clones in the entire database having band b and nmean as the mean number of bands in the clone]. Taking band abundances into account satisfies the additive condition, when the sum of weights of two bands is equal to the weight of "pair of bands" that appears with an abundance equal to the product of abundances of the bands (because bands are supposed to be independent).


In contrast to FPC, LTC excludes putatively false significant overlaps and putatively problematic clones before clustering. The main idea behind the identification of problematic clones and clone overlaps is that each part of the chromosome is most probably covered by several clones (although in fact, some parts can be uncovered or poorly covered by clones of the BAC library). One can expect that chimerical clones and false clone overlaps are not proven by parallel clones [39, 52]. Thus, clustering should subdivide the clones into groups covering different parts of the chromosome. LTC clusters the clones in such a way that each position of a chromosomal region (without ends), covered by clones from the cluster, is covered by several (at least by three) significantly overlapping clones. Moreover, it requires that, even after excluding any single clone or clone overlap, for any pair of clones c i and c j from the cluster C0, a sequence of clones c(1),..,c( n ) from C0 should exist such that c(1) = c i , c( n ) = c j and overlap of clones c( k ) and c( k +1) is significant for all k = 1,..,n-1.


(iii) Clustering with "adaptively" varying cutoff


Figure 1

Scheme of clone clustering with adapting cutoff. Diamonds denote single-linkage clustering with corresponding cutoff. Circles denote procedure of excluding clones and clone overlaps not proved by parallel paths in the net of significant (relative to the corresponding cutoff) clone overlaps from the analysis.

(iv) Looking for linear topological structure

Figure 2

Problematic clusters with non-linear topological structure. (a) Identification of non-linearity of cluster topological structure: presence of vertices with not too small ranks (e.g., more than 2) points to non-short offshoots from the selected diametric path (marked in bold line). (b) Splitting clusters into sub-clusters having linear topological structure. See also Additional File 1, Section 4.

(v) Ordering using global optimization

W ( Ω ) = Σ k = 1 , .. , n 1 W Ω ( k ) , Ω ( k + 1 ) b ( Ω ) W 0 ,

where Wi,j= -log Pr(c i , c j ), b(Ω) is the number of adjacent (within ordering Ω) clones with Pr(cΩ( k ), cΩ( k +1)) > Pr0 and W0 is the penalty for non-significant overlap of adjacent clones.

The maximization of such criterion can be reformulated as the well-known and intensively studied Traveling Salesman Problem (TSP) without the need to return to the starting point. Let Wmax be the maximum of Wi,j= -log Pr(c i , c j ). LTC defines distance between two clones as
d ( c i , c j ) = W max W i , j + W 0 1 { P r ( c i , c j ) > P r 0 } ,

where 1{Pr(c i , c j ) > Pr0} is indicator function equal to 1, if Pr(c i , c j ) > Pr0, and equal to zero otherwise. Global optimization is effective especially when marker information is also available [46]. The exact solution to the TSP is a computationally challenging problem. Nevertheless, good heuristics (e.g., based on evolution strategy optimization) for the solution of TSP were developed for situations where the number of vertices is up to 103 orders of magnitude [58]. Coordinates of clone ends within the contig based on the solution path Ω best can be calculated by methods proposed by Flibotte et al. (2004) [46]. Using such global optimization approach can result in a reduced number of Q-clones and of places in the contig where two neighbor clones have an unexpected non-significant overlap. More effective triplewise linking distance also can be used to reduce the effect of false positive and false negative bands [39].

(vi) Resampling verification of ordering


(vii) Merging of sub-contigs


(viii) MTP establishment


II. Verification and improvement of FPC contigs


Comparison of clone partitions


Graphical representation of the cluster topological structure


Simulation of BAC libraries based on the known genome sequences


Fingerprint for generated clones were defined by the set of bands of K types (corresponding to K used protruding-end restriction enzymes) presented in the clone; we used enzymes BamHI, EcoRI, XbaI and XhoI (K = 4) analogously to Ding et al. (1999) [21]. Presence of a band b with length L b and type k b is defined by the presence of sequence part of length L b bp bounded by the restriction site of enzyme k b from the one side and restriction site of one of the K enzymes mentioned above, or restriction site of blunt-end restriction enzyme (we used HaeIII) or clone end from the another side. In fact, sequence parts bounded by two different protruding-end restriction enzymes are twice included into fingerprint. Bands with length <Lmin = 50 bp or >Lmin = 500 were filtered out. Clones with number of bands n < nmin = 50 or n > nmax = 250 were also filtered out.

In the preparation of input data for the FPC and LTC programs we introduced noise into sequence length scoring to simulate errors in wet fingerprinting process. "Observed" band length was calculated by L b + err, where err is a random value uniformly distributed within interval (-ε, ε) or within (-3ε, 3ε) with probabilities p ε = 0.90 and p3 ε = 1-p ε = 0.1 respectively. This imples that difference between two observations of the same band is less than constant tolerance value t with probability τ = p ε 2(1-(1-t/2ε)2) + p3 ε 2(1-(1-t/6ε)2) + 2p ε p3 ε (t/3ε). We used ε = t/ 2 = 0.2 implying τ = 0.94. To satisfy FPC format, band lengths were multiplied by 30 and rounded (hence tolerance t = 12). Type of band was taken into account by adding 0, 5000, 10000 or 15000 for the resulted band length for bands of type k = 1, 2, 3 and 4, respectively. Some bands of clones were excluded (with probability pmissing = 0.05) to simulate false negatives caused by problems in PCR reactions. Automatic FPC assembly was conducted using cutoffs 10-75 - 10-45 with step × 105 and DQer for contigs having more than 10% Q-clones (with step × 109) and ReBuild with corresponding cutoff if needed (similar to Paux et al., 2008 [48]).




Simulated BAC libraries

Simulated BAC libraries LibRiceChr1 and LibMaizeChr1 were constructed based on the known genome sequences SeqRiceChr1 and SeqMaizeChr1 for chromosome 1 of rice (45 Mbp, available at, file chr01.fa.gz) and chromosome 1 of maize (300 Mbp, available at, we used version that was downloaded at June 10, 2010), respectively. Basic characteristics of the libraries are summarized in table Table 1.
Table 1

Basic characteristics of simulated BAC-libraries


Lib RiceChr1

Lib MaizeChr1

Sequence length

45,064,769 bp

300,239,041 bp


12,570/3,585.1 bp

110,910/2,707.1 bp

NBandEnds (LBandReal)

179,050 (251.7 bp)

1,392,692 (215.6 bp)





133.3 kbp/138.1 kbp

132.0 kbp/134.5 kbp

L BandObs

1,225.9 bp

1,042.4. bp







NCh = Nch2 + Nch3 + Nch4

202 = 198 + 4 + 0

1,016 = 999 + 16 + 1

Here NBinEnds is the number of restriction sites corresponding to enzyme HindIII chosen for clone-end simulation; LBin is the mean length of bin equal to distance between restriction sites corresponding to enzyme HindIII; NBandEnds is the number of restriction sites corresponding to the enzymes BamHI, EcoRI, XbaI, XhoI and HaeIII used for fingerprinting; LBandReal is the mean distance between restriction sites corresponding to these enzyme; nMean is the mean number of bands (with length from 50 to 500 and colored end) per clone; nMeanObs is the mean observed number of bands (bands with different end-colors are taken twice, but among bands with the same color and length only one delegate is observed). LCloneObs and LClone are mean lengths of clones (with and without chimerical clones respectively); LBandObs is the mean length of bands with length from 50 to 500 bp; LBandMap is the mean length of bands used for band map length calculation (equal to LCloneObs/nMeanObs); NClonesSimul is the number of simulated clones; NClones is the number of simulated clones with observed number of bands from 50 to 250; Nch2, Nch3, and Nch4 are resulted numbers of chimerical clones with number of bands from 50 to 250 and composed by union of 2, 3 and 4 parts, respectively.

Results and Discussion

Distribution of bands and clone lengths

In total, 30 to 275 bands were scored (out of 18,000 possible) for each of the N = 56,952 clones of the 3B BAC library (for more details of this data see [48]). The frequency of a band b was calculated as π b = N b /N, where N b is the number of clones containing bands with lengths different from b not more than the tolerance value. The bands showed quite variable abundances (Additional File 2, Fig. AF2.3a). In particular, one band was observed with π b = 0.93, one with π b = 0.78, six with π b from 0.2 up to 0.32, 220 with π b from 0.1 up to 0.2, 654 with π b from 0.05 up to 0.1, and others were observed in less than 5% of the clones. The minimal band abundance was 1.2%. We found more than 30 of the five-band combinations ("band haplotypes") present in multiple clones in a range of 1000-2271 (3.6% of total) clones, where π b of bands was in the range of 0.120 to 0.156, pointing to highly significant "linkage disequilibria" of the bands. This can result from physical overlap of considered clones and from repeats [6, 64]. The distribution of clone length (scored as number of bands) was bimodal (Additional File 2, Fig. AF2.3b). The origin of this bimodality is in the construction of the BAC library itself. Three sub-libraries were constructed including large, medium, and small fragments (see [65]). Fingerprinting results revealed that the medium length sub-library was actually a mix of large and small inserts, and not medium inserts. This resulted in two distinct populations of clone length.

LTC, a new algorithm for building contigs from fingerprinted clones



(i) Identification of significant clone overlaps by LTC

Figure 3

Comparison of metrics: (a) Number of significant clone overlaps K per clone for different cutoffs. Using liberal cutoffs P0(Snid)= 10-12, P0(Sulst)= 10-17.2, and P0(Siid)= 10-19.4 give about the same number of significant clone overlaps (~ 12.7 per clone). (b) Pr(Sulst)vs. Pr(Snid). Dots in rectangle I correspond to clone overlaps significantly relative to Pr(Sulst)= 10-17.2 but not significantly relative to Pr(Snid)= 10-12 (false positives). Dots in rectangle I correspond to clone overlaps significantly relative to Pr(Sulst)= 10-17.2 but not significantly relative to Pr(Snid)= 10-12 (false positives). Dots in rectangle IV correspond to clone overlaps significantly relative to Pr(Snid)= 10-12 but not significant relatively to Pr(Sulst)= 10-17.2 (false negatives).



(ii) Clustering the 3B fingerprinting dataset: comparing different procedures

Partition of clones using the LTC adaptive clustering procedure
Figure 4

Adaptive clustering using different scenarios: (a) full scheme (see Fig. 1); (b) reduced scheme (TENPP procedure used only once); (c) clustering with adaptively changing cutoffs (for simplicity, only cutoffs 10-12, 10-25, 10-35, 10-45, and 10-50 were used in the example); (d) clustering with uniform stringent cutoff 10-50 (non-adaptive clustering analogous to FPC). Clustering (a) and (b) were based on P(SnidM); clustering (c) and (d) were based on P(Snid).K - number of significant clone overlaps; n - number of clones in clusters of reasonable size (from 6 to 500); ∑n - total number of clones in clusters of reasonable size; N ¯ - number of clones in clusters with less than 6 clones, singletons, or clones excluded by TENPP procedures; K ¯ - number of significant clone overlaps excluded by TENPP procedures; k - number of clusters of reasonable size; M = ∑n/k - mean number of clones in clusters of reasonable size; N = 56,952 is the total number of clones in the database; N i -number of clones in the large or intermediate size cluster i.





Skipping some components of the LTC clustering algorithm
To demonstrate the power of the LTC adaptive clustering procedure, we skipped some of the clustering scheme components described above (Figure 4a). Three versions were considered: (i) using TENPP only once; (ii) clustering with adaptively changing cutoff stringency but without the TENPP procedure; and (iii) clustering with a uniformly stringent cutoff (analogous to the FPC algorithm).
  1. (i)

    Figure 4b shows that if the TENPP is used only once (with cutoff Pr 0 = 10-12) then in addition to reasonable size clusters, clustering with cutoff Pr 1 = 10-15 results also in two large (with 3,428 and 1,399 clones) and two intermediate size (with 880 and 615 clones) clusters. Repeated clustering with the more stringent cutoff Pr 2 = 10-18 gives additional reasonable size clusters plus one large cluster with 2,878 clones and two intermediate size clusters (with 640 and 615 clones) (Figure 4b). Further increase of the cutoff stringency up to Pr 3 = 10-21 splits these clusters into one large cluster with 1,900 clones and two intermediate size clusters (with 625 and 613 clones, Figure 4b). The clone partition obtained with this scenario was called C 1.

  2. (ii)

    Without using the TENPP procedure (Figure 4c), one very large cluster is obtained even for very stringent cutoffs (e.g., 51,780 for Pr 0 = 10-12, 48,577 for Pr 1 = 10-25, 41,527 for Pr 2 = 10-35, and 19,590 for Pr 3 = 10-45). This clone partition was called C 2.

  3. (iii)

    Clustering with a stringent uniform cutoff (10-50) (Figure 4d) resulted in more singletons and smaller clusters compared to clustering with adaptively changing cutoff (Figure 4c). The clone partition obtained with the uniform cutoff will be referred to as C 3, whereas the partition obtained with FPC (after ordering and merging) will be called C FPC. In partition C FPC, 41,295 of the 56,952 BAC clones were automatically subdivided into 1,995 contigs (with 6 and more clones) that were manually merged into 1,036 contigs with 6 to 290 clones per contig; the remaining 15,675 clones were found in clusters with less than 6 clones or were singletons [48].



Comparing LTC vs. FPC clustering


(iii) Verification of FPC contigs


Contig consisting of two non-connected parts


Buried clones causing conflicts between ordering and contig connectivity
The significance of clone overlap is determined by the number of common bands and clone lengths. Hence, if clone c i is buried in clone c j and significantly overlaps with clone c k ,, then it is not necessary that the overlap of clones c i and c k is also significant (see Figure 5a). Thus, after excluding buried clones, the net of significant clone overlaps can lose its connectivity (see Figure 5b). On the other hand, it is likely that each path along the net of significant connections, that visits all vertices, will visit the vertex corresponding to clone c i , buried in clone c j , before and after visiting the vertex corresponding to clone c j (see Figure 5c). In other words, vertex corresponding to clone c j is visited twice, and therefore, such paths cannot be found directly by tools constructed for solving the classical TSP. Such a situation was found in 12 contigs and could be solved by temporal exclusion of only a subset of buried clones from the cluster before ordering.
Figure 5

Examples of situations where buried clones cause problems in clone ordering by LTC. (a) Clone c i is buried in clone c j and significantly overlaps with clone c k , but overlap of clones c i and c k is not significant. (b) The net of significant clone overlaps for the situation (a). Exclusion of buried clone c i leads to a loss of connection between the left and right parts of the net. (c) Clones cannot be ordered to fit the requirement that adjacent clones overlap significantly (because the buried clone significantly overlapped with one clone only).

Weak power of ordering tools based on local optimization


Topologically non-linear structure of the contig
Figure 6

Net representation of problematic FPC contigs with non-linear topological structure. Presented four contigs from the 3BL7-0.63-1.00 and 3BS1-0.33-0.55 deletion bins display non-linear topological structures. Vertices represent clones; edges represent significant (relative to arbitrary selected cutoff Pr0(SnidM)= 10-12) clone overlaps. Branching regions are marked by solid black circle.

Non-synchronous utilization of information on common markers and common bands


(iv) Elongation of FPC contigs by using LTC

Figure 7



Table 2

Contig assembly with FPC and LTC programs


Lib RiceChr1

Lib MaizeChr1






NClonesCtg /NClones (%)

4,293/4,417 (97.2%)

4,231/4,417 (95.7%)

28,899/29,924 (96.6%)

28,994/29,924 (96.9%)

N Ctgs





N MeanClonesCtg





L MeanClonesCtg

1,045 kbp

1,731 kbp

1,128 kbp

1,532 kbp


183/202 (91%)

22/202 (11%)

946/1,016 (93%)

196/1,016 (19%)


105/124 (85%)

106/186 (57%)

955/1,025 (93%)

110/930 (19%)


8/42 (19%)


23/257 (9%)



22/42 (52%)




n CtgParts






4/20 (20%)

1/25 (4%)

47/149 (32%)

4/190 (2%)

Here NClonesCtg is the total number of clones in contigs with 6 clones and more (others were excluded from the analysis); NCtgs is the number of contigs with 6 clones and more; NMeanClonesCtg is the mean number of clones in the contigs with 6 clones and more; LMeanClonesCtg = LCloneObs NMeanClonesCtg/Covarege is estimated mean length of the contigs with 6 clones and more; NChCtg is the number of chimerical clones in the contigs with 6 clones and more (false negatives in the procedure of Q-clone detection); NQNotCh is the number of non-chimerical clones that were identified as Q-clones (false positives); NQ is the number of clones that were not included into contigs; NCtgsNonLinear is the number of contigs with non-linear topological structure; NCtgCh is the number of contigs containing clones (except chimerical ones) from non-overlapping parts; nCtgParts is the mean number of non-overlapping parts per contig; NCtgOrdWrong is the number of continuous contigs with errors in clone ordering.



General discussion









The research leading to these results has received funding from the European Community's Seventh Framework Programme (FP7/2007-2013) under the grant agreement FP7-212019 (TriticeaeGenome project, It was also partially supported by Binational Agricultural Research and Development Fund (BARD research project US-3873-06) and by the Israeli Ministry of Absorption.

Authors’ Affiliations

Institute of Evolution, University of Haifa
INRA, Genetics, Diversity and Ecophysiology of Cereals


  2. McPherson JD, Marra M, Hillier L, Waterston RH, Chinwalla A, Wallis J, Sekhon M, Wylie K, Mardis ER, Wilson RK, Fulton R, Kucaba TA, Wagner-McPherson C, Barbazuk WB, Gregory SG, Humphray SJ, French L, Evans RS, Bethel G, Whittaker A, Holden JL, McCann OT, Dunham A, Soderlund C, Scott CE, Bentley DR, Schuler G, Chen HC, Jang W, Green ED, et al.: A physical map of the human genome. Nature 2001, 409(6822):934–941. 10.1038/35057157View ArticlePubMedGoogle Scholar
  3. Gregory SG, Sekhon M, Schein J, Zhao S, Osoegawa K, Scott CE, Evans RS, Burridge PW, Cox TV, Fox CA, Hutton RD, Mullenger IR, Phillips KJ, Smith J, Stalker J, Threadgold GJ, Birney E, Wylie K, Chinwalla A, Wallis J, Hillier L, Carter J, Gaige T, Jaeger S, Kremitzki C, Layman D, Maas J, McGrane R, Mead K, Walker R, et al.: A physical map of the mouse genome. Nature 2002, 418(6899):743–750. 10.1038/nature00957View ArticlePubMedGoogle Scholar
  4. Chen M, Presting G, Barbazuk WB, Goicoechea JL, Blackmon B, Fang G, Kim H, Frisch D, Yu Y, Sun S, Higingbottom S, Phimphilai J, Phimphilai D, Thurmond S, Gaudette B, Li P, Liu J, Hatfield J, Main D, Farrar K, Henderson C, Barnett L, Costa R, Williams B, Walser S, Atkins M, Hall C, Budiman MA, Tomkins JP, Luo M, et al.: An integrated physical and genetic map of the rice genome. Plant Cell 2002, 14(3):537–545. 10.1105/tpc.010485View ArticlePubMedPubMed CentralGoogle Scholar
  5. Coe E, Cone K, McMullen M, Chen SS, Davis G, Gardiner J, Liscum E, Polacco M, Paterson A, Sanchez-Villeda H, Soderlund C, Wing R: Access to the maize genome: an integrated physical and genetic map. Plant Physiol 2002, 128(1):9–12. 10.1104/pp.010953View ArticlePubMedPubMed CentralGoogle Scholar
  6. Nelson WM, Bharti AK, Butler E, Wei F, Fuks G, Kim H, Wing RA, Messing J, Soderlund C: Whole-genome validation of high-information-content fingerprinting. Plant Physiol 2005, 139(1):27–38. 10.1104/pp.105.061978View ArticlePubMedPubMed CentralGoogle Scholar
  7. Lewin HA, Larkin DM, Pontius J, O'Brien SJ: Every genome sequence needs a good map. Genome Res 2009, 19(11):1925–1928. 10.1101/gr.094557.109View ArticlePubMedPubMed CentralGoogle Scholar
  8. Staden R: A strategy of DNA sequencing employing computer programs. Nucleic Acids Res 1979, 6(7):2601–2610. 10.1093/nar/6.7.2601View ArticlePubMedPubMed CentralGoogle Scholar
  9. Roach JC, Boysen C, Wang K, Hood L: Pairwise end sequencing: a unified approach to genomic mapping and sequencing. Genomics 1995, 26(2):345–353. 10.1016/0888-7543(95)80219-CView ArticlePubMedGoogle Scholar
  10. Fleischmann RD, Adams MD, White O, Clayton RA, Kirkness EF, Kerlavage AR, Bult CJ, Tomb JF, Dougherty BA, Merrick JM: Whole-genome random sequencing and assembly of Haemophilus influenzae Rd. Science 1995, 269(5223):496–512. 10.1126/science.7542800View ArticlePubMedGoogle Scholar
  11. Adams MD, Celniker SE, Holt RA, Evans CA, Gocayne JD, Amanatides PG, Scherer SE, Li PW, Hoskins RA, Galle RF, George RA, Lewis SE, Richards S, Ashburner M, Henderson SN, Sutton GG, Wortman JR, Yandell MD, Zhang Q, Chen LX, Brandon RC, Rogers YH, Blazej RG, Champe M, Pfeiffer BD, Wan KH, Doyle C, Baxter EG, Helt G, Nelson CR, et al.: The genome sequence of Drosophila melanogaster. Science 2000, 287(5461):2185–2195. 10.1126/science.287.5461.2185View ArticlePubMedGoogle Scholar
  12. Voelkerding KV, Dames SA, Durtschi JD: Next-generation sequencing: from basic research to diagnostics. Clin Chem 2009, 55(4):641–658. 10.1373/clinchem.2008.112789View ArticlePubMedGoogle Scholar
  13. Li R, Fan W, Tian G, Zhu H, He L, Cai J, Huang Q, Cai Q, Li B, Bai Y, Zhang Z, Zhang Y, Wang W, Li J, Wei F, Li H, Jian M, Li J, Zhang Z, Nielsen R, Li D, Gu W, Yang Z, Xuan Z, Ryder OA, Leung FC, Zhou Y, Cao J, Sun X, Fu Y, et al.: The sequence and de novo assembly of the giant panda genome. Nature 2010, 463(7279):311–317. 10.1038/nature08696View ArticlePubMedPubMed CentralGoogle Scholar
  14. Metzker ML: Sequencing technologies - the next generation. Nat Rev Genet 2010, 11(1):31–46. 10.1038/nrg2626View ArticlePubMedGoogle Scholar
  15. Coulson A, Sulston J, Brenner S, Karn J: Toward a physical map of the genome of the nematode Caenorhabditis elegans. Proc Natl Acad Sci USA 1986, 83(20):7821–7825. 10.1073/pnas.83.20.7821View ArticlePubMedPubMed CentralGoogle Scholar
  16. Olson MV, Dutchik JE, Graham MY, Brodeur GM, Helms C, Frank M, MacCollin M, Scheinman R, Frank T: Random-clone strategy for genomic restriction mapping in yeast. Proc Natl Acad Sci USA 1986, 83(20):7826–7830. 10.1073/pnas.83.20.7826View ArticlePubMedPubMed CentralGoogle Scholar
  17. Sulston J, Mallett F, Staden R, Durbin R, Horsnell T, Coulson A: Software for genome mapping by fingerprinting techniques. Comput Appl Biosci 1988, 4(1):125–132.PubMedGoogle Scholar
  18. Gregory SG, Howell GR, Bentley DR: Genome mapping by fluorescent fingerprinting. Genome Res 1997, 7(12):1162–1168.PubMedPubMed CentralGoogle Scholar
  19. Marra MA, Kucaba TA, Dietrich NL, Green ED, Brownstein B, Wilson RK, McDonald KM, Hillier LW, McPherson JD, Waterston RH: High throughput fingerprint analysis of large-insert clones. Genome Res 1997, 7(11):1072–1084.PubMedPubMed CentralGoogle Scholar
  20. Zhang HB, Wing RA: Physical mapping of the rice genome with BACs. Plant Mol Biol 1997, 35(1–2):115–127. 10.1023/A:1005733909099View ArticlePubMedGoogle Scholar
  21. Ding Y, Johnson MD, Colayco R, Chen YJ, Melnyk J, Schmitt H, Shizuya H: Contig assembly of bacterial artificial chromosome clones through multiplexed fluorescence-labeled fingerprinting. Genomics 1999, 56(3):237–246. 10.1006/geno.1998.5734View ArticlePubMedGoogle Scholar
  22. Luo MC, Thomas C, You FM, Hsiao J, Ouyang S, Buell CR, Malandro M, McGuire PE, Anderson OD, Dvorak J: High-throughput fingerprinting of bacterial artificial chromosomes using the snapshot labeling kit and sizing of restriction fragments by capillary electrophoresis. Genomics 2003, 82(3):378–389. 10.1016/S0888-7543(03)00128-9View ArticlePubMedGoogle Scholar
  23. Venter JC, Smith HO, Hood L: A new strategy for genome sequencing. Nature 1996, 381(6581):364–366. 10.1038/381364a0View ArticlePubMedGoogle Scholar
  24. Prade RA, Griffith J, Kochut K, Arnold J, Timberlake WE: In vitro reconstruction of the Aspergillus (= Emericella) nidulans genome. Proc Natl Acad Sci USA 1997, 94(26):14564–14569. 10.1073/pnas.94.26.14564View ArticlePubMedPubMed CentralGoogle Scholar
  25. Mahairas GG, Wallace JC, Smith K, Swartzell S, Holzman T, Keller A, Shaker R, Furlong J, Young J, Zhao S, Adams MD, Hood L: Sequence-tagged connectors: a sequence approach to mapping and scanning the human genome. Proc Natl Acad Sci USA 1999, 96(17):9739–9744. 10.1073/pnas.96.17.9739View ArticlePubMedPubMed CentralGoogle Scholar
  26. Faris JD, Gill BS: Genomic targeting and high-resolution mapping of the domestication gene Q in wheat. Genome 2002, 45(4):706–718. 10.1139/g02-036View ArticlePubMedGoogle Scholar
  27. Weikard R, Goldammer T, Laurent P, Womack JE, Kuehn C: A gene-based high-resolution comparative radiation hybrid map as a framework for genome sequence assembly of a bovine chromosome 6 region associated with QTL for growth, body composition, and milk performance traits. BMC Genomics 2006, 7: 53. 10.1186/1471-2164-7-53View ArticlePubMedPubMed CentralGoogle Scholar
  28. Le Cunff L, Garsmeur O, Raboin LM, Pauquet J, Telismart H, Selvi A, Grivet L, Philippe R, Begum D, Deu M, Costet L, Wing R, Glaszmann JC, D'Hont A: Diploid/polyploid syntenic shuttle mapping and haplotype-specific chromosome walking toward a rust resistance gene (Bru1) in highly polyploid sugarcane (2n approximately 12x approximately 115). Genetics 2008, 180(1):649–660. 10.1534/genetics.108.091355View ArticlePubMedPubMed CentralGoogle Scholar
  29. Wang GL, Holsten TE, Song WY, Wang HP, Ronald PC: Construction of a rice bacterial artificial chromosome library and identification of clones linked to the Xa-21 disease resistance locus. Plant J 1995, 7(3):525–533. 10.1046/j.1365-313X.1995.7030525.xView ArticlePubMedGoogle Scholar
  30. Tanksley SD, Ganal MW, Martin GB: Chromosome landing: a paradigm for map-based gene cloning in plants with large genomes. Trends Genet 1995, 11(2):63–68. 10.1016/S0168-9525(00)88999-4View ArticlePubMedGoogle Scholar
  31. Huang L, Brooks SA, Li W, Fellers JP, Trick HN, Gill BS: Map-based cloning of leaf rust resistance gene Lr21 from the large and polyploid genome of bread wheat. Genetics 2003, 164(2):655–664.PubMedPubMed CentralGoogle Scholar
  32. Ma J, SanMiguel P, Lai J, Messing J, Bennetzen JL: DNA rearrangement in orthologous orp regions of the maize, rice and sorghum genomes. Genetics 2005, 170(3):1209–1220. 10.1534/genetics.105.040915View ArticlePubMedPubMed CentralGoogle Scholar
  33. Tameling WI, Baulcombe DC: Physical association of the NB-LRR resistance protein Rx with a Ran GTPase-activating protein is required for extreme resistance to Potato virus X. Plant Cell 2007, 19(5):1682–1694. 10.1105/tpc.107.050880View ArticlePubMedPubMed CentralGoogle Scholar
  34. Monden Y, Naito K, Okumoto Y, Saito H, Oki N, Tsukiyama T, Ideta O, Nakazaki T, Wessler SR, Tanisaka T: High potential of a transposon mPing as a marker system in japonica × japonica cross in rice. DNA Res 2009, 16(2):131–140. 10.1093/dnares/dsp004View ArticlePubMedPubMed CentralGoogle Scholar
  35. Soderlund C, Longden I, Mott R: FPC: a system for building contigs from restriction fingerprinted clones. Comput Appl Biosci 1997, 13(5):523–535.PubMedGoogle Scholar
  36. Soderlund C, Humphray S, Dunham A, French L: Contigs built with fingerprints, markers, and FPC V4.7. Genome Res 2000, 10(11):1772–1787. 10.1101/gr.GR-1375RView ArticlePubMedPubMed CentralGoogle Scholar
  37. Bhandarkar SM, Machaka SA, Shete SS, Kota RN: Parallel computation of a maximum-likelihood estimator of a physical map. Genetics 2001, 157(3):1021–1043.PubMedPubMed CentralGoogle Scholar
  38. Bhandarkar S, Huang J, Arnold J: Information theoretic approach to genome reconstruction. In Handbook of computational molecular biology. Edited by: Aluru S. Chapman & Hall/CRC Computer and Information Science Series; 2006:1–26.Google Scholar
  39. Wang Y, Prade RA, Griffith J, Timberlake WE, Arnold J: A fast random cost algorithm for physical mapping. Proc Natl Acad Sci USA 1994, 91(23):11094–11098. 10.1073/pnas.91.23.11094View ArticlePubMedPubMed CentralGoogle Scholar
  40. Wendl MC: Probabilistic assessment of clone overlaps in DNA fingerprint mapping via a priori models. J Comput Biol 2005, 12(3):283–297. 10.1089/cmb.2005.12.283View ArticlePubMedGoogle Scholar
  41. Wendl MC: Algebraic correction methods for computational assessment of clone overlaps in DNA fingerprint mapping. BMC Bioinformatics 2007, 8: 127. 10.1186/1471-2105-8-127View ArticlePubMedPubMed CentralGoogle Scholar
  42. Balding DJ, Torney DC: Statistical analysis of DNA fingerprint data for ordered clone physical mapping of human chromosomes. Bull Math Biol 1991, 53(6):853–879.View ArticlePubMedGoogle Scholar
  43. Mayraz G, Shamir R: Construction of physical maps from oligonucleotide fingerprints data. J Comput Biol 1999, 6(2):237–252. 10.1089/cmb.1999.6.237View ArticlePubMedGoogle Scholar
  44. Meyers BC, Scalabrin S, Morgante M: Mapping and sequencing complex genomes: let's get physical! Nat Rev Genet 2004, 5(8):578–588. 10.1038/nrg1404View ArticlePubMedGoogle Scholar
  45. Marra M, Kucaba T, Sekhon M, Hillier L, Martienssen R, Chinwalla A, Crockett J, Fedele J, Grover H, Gund C, McCombie WR, McDonald K, McPherson J, Mudd N, Parnell L, Schein J, Seim R, Shelby P, Waterston R, Wilson R: A map for sequence analysis of the Arabidopsis thaliana genome. Nat Genet 1999, 22(3):265–270. 10.1038/10327View ArticlePubMedGoogle Scholar
  46. Flibotte S, Chiu R, Fjell C, Krzywinski M, Schein JE, Shin H, Marra MA: Automated ordering of fingerprinted clones. Bioinformatics 2004, 20(8):1264–1271. 10.1093/bioinformatics/bth079View ArticlePubMedGoogle Scholar
  47. Salzberg SL, Yorke JA: Beware of mis-assembled genomes. Bioinformatics 2005, 21(24):4320–4321. 10.1093/bioinformatics/bti769View ArticlePubMedGoogle Scholar
  49. Waterman MS, Griggs JR: Interval graphs and maps of DNA. Bull Math Biol 1986, 48(2):189–195.View ArticlePubMedGoogle Scholar
  50. Cuticchia AJ, Arnold J, Timberlake WE: The use of simulated annealing in chromosome reconstruction experiments based on binary scoring. Genetics 1992, 132(2):591–601.PubMedPubMed CentralGoogle Scholar
  51. Zhang P, Schon EA, Fischer SG, Cayanis E, Weiss J, Kistler S, Bourne PE: An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA. Comput Appl Biosci 1994, 10(3):309–317.PubMedGoogle Scholar
  52. Arratia R, Lander ES, Tavare S, Waterman MS: Genomic mapping by anchoring random clones: a mathematical analysis. Genomics 1991, 11(4):806–827. 10.1016/0888-7543(91)90004-XView ArticlePubMedGoogle Scholar
  53. Jain AK, Dubes RC: Algorithms for clustering data. N.J.: Prentice Hall: Englewood Cliffs; 1988.Google Scholar
  54. Batagelj V, Mrvar A: Pajek - analysis and visualization of large networks. In Graph drawing software. Edited by: Jünger M, Mutzel P. Berlin: Springer; 2003:77–103.Google Scholar
  55. Bollobas B: Modern graph theory. 1st edition. Springer; 2002.Google Scholar
  56. Fickett J, Cinkosky M: A genetic algorithm for assembling chromosome physical maps. In The Second International Conference on Bioinformatics. Supercomputing and Complex Genomic Analysis. Edited by: Lim H, Fickett J, Cantor C, Robbins R. New Jersey: World Scientific; 1992:273–285.Google Scholar
  57. Alizadah F, Karp R, Newberg LA, Weisser D: Physical mapping of chromosomes: A combinatorial problem in molecular biology. Algorithmica 1995, 13(Numbers 1–2):52–76. 10.1007/BF01188581View ArticleGoogle Scholar
  58. Mester D, Ronin Y, Minkov D, Nevo E, Korol A: Constructing large-scale genetic maps using an evolutionary strategy algorithm. Genetics 2003, 165(4):2269–2282.PubMedPubMed CentralGoogle Scholar
  59. Cuticchia AJ, Arnold J, Timberlake WE: ODS: ordering DNA sequences--a physical mapping algorithm based on simulated annealing. Comput Appl Biosci 1993, 9(2):215–219.PubMedGoogle Scholar
  60. Rand WM: Objective criteria for the evaluation of clustering methods. Journal of the American Statistical Association 1971, 66: 846–850. 10.2307/2284239View ArticleGoogle Scholar
  61. Kamada T, Kawai S: An algorithm for drawing general undirected graphs. Information Processing Letters 1989, 31: 7–15. 10.1016/0020-0190(89)90102-6View ArticleGoogle Scholar
  62. Xu Z, Sun S, Covaleda L, Ding K, Zhang A, Wu C, Scheuring C, Zhang HB: Genome physical mapping with large-insert bacterial clones by fingerprint analysis: methodologies, source clone genome coverage, and contig map quality. Genomics 2004, 84(6):941–951. 10.1016/j.ygeno.2004.08.014View ArticlePubMedGoogle Scholar
  63. Krzywinski M, Bosdet I, Mathewson C, Wye N, Brebner J, Chiu R, Corbett R, Field M, Lee D, Pugh T, Volik S, Siddiqui A, Jones S, Schein J, Collins C, Marra M: A BAC clone fingerprinting approach to the detection of human genome rearrangements. Genome Biol 2007, 8(10):R224. 10.1186/gb-2007-8-10-r224View ArticlePubMedPubMed CentralGoogle Scholar
  64. Nelson WM, Dvorak J, Luo MC, Messing J, Wing RA, Soderlund C: Efficacy of clone fingerprinting methodologies. Genomics 2007, 89(1):160–165. 10.1016/j.ygeno.2006.08.008View ArticlePubMedGoogle Scholar
  65. Safar J, Bartos J, Janda J, Bellec A, Kubalakova M, Valarik M, Pateyron S, Weiserova J, Tuskova R, Cihalikova J, Vrana J, Simkova H, Faivre-Rampant P, Sourdille P, Caboche M, Bernard M, Dolezel J, Chalhoub B: Dissecting large and complex genomes: flow sorting and BAC cloning of individual chromosomes from bread wheat. Plant J 2004, 39(6):960–968. 10.1111/j.1365-313X.2004.02179.xView ArticlePubMedGoogle Scholar
  66. Mester DI, Ronin YI, Korostishevsky MA, Pikus VL, Glazman AE, Korol AB: Multilocus consensus genetic maps (MCGM): formulation, algorithms, and results. Comput Biol Chem 2006, 30(1):12–20. 10.1016/j.compbiolchem.2005.09.007View ArticlePubMedGoogle Scholar
  67. Korol AB, Mester D, Frenkel Z, Ronin YI: Methods for genetic analysis in the Triticeae . In Genetics and Genomics of the Triticeae. Edited by: Feuillet C, Muehlbauer GJ. Springer + Business Media LLC; 2009:163–199. full_textView ArticleGoogle Scholar


© Frenkel et al; licensee BioMed Central Ltd. 2010
