DOI: 10.1186/gb-2009-10-3-r25. Ultrafast and memory-efficient alignment of short DNA sequences to the human genome

Ultrafast and memory-efficient alignment of short DNA sequences to the human genome

10.1186/gb-2009-10-3-r25

Crossref journal-article

Springer Science and Business Media LLC

Genome Biology (297)

Abstract

AbstractBowtie is an ultrafast, memory-efficient alignment program for aligning short DNA sequence reads to large genomes. For the human genome, Burrows-Wheeler indexing allows Bowtie to align more than 25 million reads per CPU hour with a memory footprint of approximately 1.3 gigabytes. Bowtie extends previous Burrows-Wheeler techniques with a novel quality-aware backtracking algorithm that permits mismatches. Multiple processor cores can be used simultaneously to achieve even greater alignment speeds. Bowtie is open source http://bowtie.cbcb.umd.edu.

Bibliography

Langmead, B., Trapnell, C., Pop, M., & Salzberg, S. L. (2009). Ultrafast and memory-efficient alignment of short DNA sequences to the human genome. Genome Biology, 10(3).

Authors 4

Ben Langmead (first)
Cole Trapnell (additional)
Mihai Pop (additional)
Steven L Salzberg (additional)

References 30 Referenced 19,048

Down TA, Rakyan VK, Turner DJ, Flicek P, Li H, Kulesha E, Graf S, Johnson N, Herrero J, Tomazou EM, Thorne NP, Backdahl L, Herberth M, Howe KL, Jackson DK, Miretti MM, Marioni JC, Birney E, Hubbard TJ, Durbin R, Tavare S, Beck S: A Bayesian deconvolution strategy for immunoprecipitation-based DNA methylome analysis. Nat Biotechnol. 2008, 26: 779-785. 10.1038/nbt1414. (10.1038/nbt1414) / Nat Biotechnol by TA Down (2008)
Johnson DS, Mortazavi A, Myers RM, Wold B: Genome-wide mapping of in vivo protein-DNA interactions. Science. 2007, 316: 1497-1502. 10.1126/science.1141319. (10.1126/science.1141319) / Science by DS Johnson (2007)
Marioni JC, Mason CE, Mane SM, Stephens M, Gilad Y: RNA-seq: an assessment of technical reproducibility and comparison with gene expression arrays. Genome Res. 2008, 18: 1509-1517. 10.1101/gr.079558.108. (10.1101/gr.079558.108) / Genome Res by JC Marioni (2008)
Bentley DR, Balasubramanian S, Swerdlow HP, Smith GP, Milton J, Brown CG, Hall KP, Evers DJ, Barnes CL, Bignell HR, Boutell JM, Bryant J, Carter RJ, Keira Cheetham R, Cox AJ, Ellis DJ, Flatbush MR, Gormley NA, Humphray SJ, Irving LJ, Karbelashvili MS, Kirk SM, Li H, Liu X, Maisinger KS, Murray LJ, Obradovic B, Ost T, Parkinson ML, Pratt MR, et al: Accurate whole human genome sequencing using reversible terminator chemistry. Nature. 2008, 456: 53-59. 10.1038/nature07517. (10.1038/nature07517) / Nature by DR Bentley (2008)
Ley TJ, Mardis ER, Ding L, Fulton B, McLellan MD, Chen K, Dooling D, Dunford-Shore BH, McGrath S, Hickenbotham M, Cook L, Abbott R, Larson DE, Koboldt DC, Pohl C, Smith S, Hawkins A, Abbott S, Locke D, Hillier LW, Miner T, Fulton L, Magrini V, Wylie T, Glasscock J, Conyers J, Sander N, Shi X, Osborne JR, Minx P, et al: DNA sequencing of a cytogenetically normal acute myeloid leukaemia genome. Nature. 2008, 456: 66-72. 10.1038/nature07485. (10.1038/nature07485) / Nature by TJ Ley (2008)
Wang J, Wang W, Li R, Li Y, Tian G, Goodman L, Fan W, Zhang J, Li J, Zhang J, Guo Y, Feng B, Li H, Lu Y, Fang X, Liang H, Du Z, Li D, Zhao Y, Hu Y, Yang Z, Zheng H, Hellmann I, Inouye M, Pool J, Yi X, Zhao J, Duan J, Zhou Y, Qin J, et al: The diploid genome sequence of an Asian individual. Nature. 2008, 456: 60-65. 10.1038/nature07484. (10.1038/nature07484) / Nature by J Wang (2008)
Li H, Ruan J, Durbin R: Mapping short DNA sequencing reads and calling variants using mapping quality scores. Genome Res. 2008, 18: 1851-1858. 10.1101/gr.078212.108. (10.1101/gr.078212.108) / Genome Res by H Li (2008)
Li R, Li Y, Kristiansen K, Wang J: SOAP: short oligonucleotide alignment program. Bioinformatics. 2008, 24: 713-714. 10.1093/bioinformatics/btn025. (10.1093/bioinformatics/btn025) / Bioinformatics by R Li (2008)
Kaiser J: DNA sequencing. A plan to capture human diversity in 1000 genomes. Science. 2008, 319: 395-10.1126/science.319.5862.395. (10.1126/science.319.5862.395) / Science by J Kaiser (2008)
Smith AD, Xuan Z, Zhang MQ: Using quality scores and longer reads improves accuracy of Solexa read mapping. BMC Bioinformatics. 2008, 9: 128-10.1186/1471-2105-9-128. (10.1186/1471-2105-9-128) / BMC Bioinformatics by AD Smith (2008)
Lin H, Zhang Z, Zhang MQ, Ma B, Li M: ZOOM! Zillions Of Oligos Mapped. Bioinformatics. 2008, 24: 2431-2437. 10.1093/bioinformatics/btn416. (10.1093/bioinformatics/btn416) / Bioinformatics by H Lin (2008)
SHRiMP - SHort Read Mapping Package. [http://compbio.cs.toronto.edu/shrimp/]
Baeza-Yates RA, Perleberg CH: Fast and practical approximate string matching. Inf Process Lett. 1996, 59: 21-27. 10.1016/0020-0190(96)00083-X. (10.1016/0020-0190(96)00083-X) / Inf Process Lett by RA Baeza-Yates (1996)
Burkhardt S, Kärkkäinen J: Better Filtering with Gapped q-Grams. Fundam Inf. 2003, 56: 51-70. / Fundam Inf by S Burkhardt (2003)
Ma B, Tromp J, Li M: PatternHunter: faster and more sensitive homology search. Bioinformatics. 2002, 18: 440-445. 10.1093/bioinformatics/18.3.440. (10.1093/bioinformatics/18.3.440) / Bioinformatics by B Ma (2002)
Smith TF, Waterman MS: Identification of common molecular subsequences. J Mol Biol. 1981, 147: 195-197. 10.1016/0022-2836(81)90087-5. (10.1016/0022-2836(81)90087-5) / J Mol Biol by TF Smith (1981)
Burrows M, Wheeler DJ: A Block Sorting Lossless Data Compression Algorithm. Technical Report 124. 1994, Palo Alto, CA: Digital Equipment Corporation / A Block Sorting Lossless Data Compression Algorithm. Technical Report 124 by M Burrows (1994)
Ferragina P, Manzini G: Opportunistic data structures with applications. [http://web.unipmn.it/~manzini/papers/focs00draft.pdf]
Ferragina P, Manzini G: An experimental study of an opportunistic index. Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete algorithms. 2001, Washington, DC: Society for Industrial and Applied Mathematics, 269-278. / Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete algorithms by P Ferragina (2001)
Healy J, Thomas EE, Schwartz JT, Wigler M: Annotating large genomes with exact word matches. Genome Res. 2003, 13: 2306-2315. 10.1101/gr.1350803. (10.1101/gr.1350803) / Genome Res by J Healy (2003)
Lippert RA: Space-efficient whole genome comparisons with Burrows-Wheeler transforms. J Comput Biol. 2005, 12: 407-415. 10.1089/cmb.2005.12.407. (10.1089/cmb.2005.12.407) / J Comput Biol by RA Lippert (2005)
Graf S, Nielsen FG, Kurtz S, Huynen MA, Birney E, Stunnenberg H, Flicek P: Optimized design and assessment of whole genome tiling arrays. Bioinformatics. 2007, 23: i195-i204. 10.1093/bioinformatics/btm200. (10.1093/bioinformatics/btm200) / Bioinformatics by S Graf (2007)
Lam TW, Sung WK, Tam SL, Wong CK, Yiu SM: Compressed indexing and local alignment of DNA. Bioinformatics. 2008, 24: 791-797. 10.1093/bioinformatics/btn032. (10.1093/bioinformatics/btn032) / Bioinformatics by TW Lam (2008)
Ewing B, Green P: Base-calling of automated sequencer traces using phred. II. Error probabilities. Genome Res. 1998, 8: 186-194. (10.1101/gr.8.3.186) / Genome Res by B Ewing (1998)
Bowtie: An ultrafast memory-efficient short read aligner. [http://bowtie.cbcb.umd.edu/]
Campbell PJ, Stephens PJ, Pleasance ED, O'Meara S, Li H, Santarius T, Stebbings LA, Leroy C, Edkins S, Hardy C, Teague JW, Menzies A, Goodhead I, Turner DJ, Clee CM, Quail MA, Cox A, Brown C, Durbin R, Hurles ME, Edwards PA, Bignell GR, Stratton MR, Futreal PA: Identification of somatically acquired rearrangements in cancer using genome-wide massively parallel paired-end sequencing. Nat Genet. 2008, 40: 722-729. 10.1038/ng.128. (10.1038/ng.128) / Nat Genet by PJ Campbell (2008)
Holt KE, Parkhill J, Mazzoni CJ, Roumagnac P, Weill FX, Goodhead I, Rance R, Baker S, Maskell DJ, Wain J, Dolecek C, Achtman M, Dougan G: High-throughput sequencing provides insights into genome variation and evolution in Salmonella typhi. Nat Genet. 2008, 40: 987-993. 10.1038/ng.195. (10.1038/ng.195) / Nat Genet by KE Holt (2008)
Nagalakshmi U, Wang Z, Waern K, Shou C, Raha D, Gerstein M, Snyder M: The transcriptional landscape of the yeast genome defined by RNA sequencing. Science. 2008, 320: 1344-1349. 10.1126/science.1158441. (10.1126/science.1158441) / Science by U Nagalakshmi (2008)
Kärkkäinen J: Fast BWT in small space by blockwise suffix sorting. Theor Comput Sci. 2007, 387: 249-257. (10.1016/j.tcs.2007.07.018) / Theor Comput Sci by J Kärkkäinen (2007)
Doring A, Weese D, Rausch T, Reinert K: SeqAn an efficient, generic C++ library for sequence analysis. BMC Bioinformatics. 2008, 9: 11-10.1186/1471-2105-9-11. (10.1186/1471-2105-9-11) / BMC Bioinformatics by A Doring (2008)

Dates

Type	When
Created	16 years, 6 months ago (March 4, 2009, 2:13 p.m.)
Deposited	10 months, 4 weeks ago (Oct. 8, 2024, 6:17 a.m.)
Indexed	37 minutes ago (Sept. 7, 2025, 9:43 a.m.)
Issued	16 years, 6 months ago (March 4, 2009)
Published	16 years, 6 months ago (March 4, 2009)
Published Online	16 years, 6 months ago (March 4, 2009)

Funders 0

None

BibTeX

@article{Langmead_2009, title={Ultrafast and memory-efficient alignment of short DNA sequences to the human genome}, volume={10}, ISSN={1474-760X}, url={http://dx.doi.org/10.1186/gb-2009-10-3-r25}, DOI={10.1186/gb-2009-10-3-r25}, number={3}, journal={Genome Biology}, publisher={Springer Science and Business Media LLC}, author={Langmead, Ben and Trapnell, Cole and Pop, Mihai and Salzberg, Steven L}, year={2009}, month=mar }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        9,
        7
      ]
    ],
    "date-time": "2025-09-07T13:43:47Z",
    "timestamp": 1757252627485
  },
  "reference-count": 30,
  "publisher": "Springer Science and Business Media LLC",
  "issue": "3",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2009,
            3,
            4
          ]
        ],
        "date-time": "2009-03-04T00:00:00Z",
        "timestamp": 1236124800000
      },
      "content-version": "tdm",
      "delay-in-days": 0,
      "URL": "http://creativecommons.org/licenses/by/2.0/"
    },
    {
      "start": {
        "date-parts": [
          [
            2009,
            3,
            4
          ]
        ],
        "date-time": "2009-03-04T00:00:00Z",
        "timestamp": 1236124800000
      },
      "content-version": "vor",
      "delay-in-days": 0,
      "URL": "http://creativecommons.org/licenses/by/2.0/"
    }
  ],
  "content-domain": {
    "domain": [
      "link.springer.com"
    ],
    "crossmark-restriction": false
  },
  "abstract": "<jats:title>Abstract</jats:title><jats:p>Bowtie is an ultrafast, memory-efficient alignment program for aligning short DNA sequence reads to large genomes. For the human genome, Burrows-Wheeler indexing allows Bowtie to align more than 25 million reads per CPU hour with a memory footprint of approximately 1.3 gigabytes. Bowtie extends previous Burrows-Wheeler techniques with a novel quality-aware backtracking algorithm that permits mismatches. Multiple processor cores can be used simultaneously to achieve even greater alignment speeds. Bowtie is open source <jats:ext-link xmlns:xlink=\"http://www.w3.org/1999/xlink\" ext-link-type=\"uri\" xlink:href=\"http://bowtie.cbcb.umd.edu\">http://bowtie.cbcb.umd.edu</jats:ext-link>.</jats:p>",
  "DOI": "10.1186/gb-2009-10-3-r25",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2009,
        3,
        4
      ]
    ],
    "date-time": "2009-03-04T19:13:36Z",
    "timestamp": 1236194016000
  },
  "update-policy": "http://dx.doi.org/10.1007/springer_crossmark_policy",
  "source": "Crossref",
  "is-referenced-by-count": 19048,
  "title": "Ultrafast and memory-efficient alignment of short DNA sequences to the human genome",
  "prefix": "10.1186",
  "volume": "10",
  "author": [
    {
      "given": "Ben",
      "family": "Langmead",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "Cole",
      "family": "Trapnell",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Mihai",
      "family": "Pop",
      "sequence": "additional",
      "affiliation": []
    },
    {
      "given": "Steven L",
      "family": "Salzberg",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "297",
  "published-online": {
    "date-parts": [
      [
        2009,
        3,
        4
      ]
    ]
  },
  "reference": [
    {
      "key": "2175_CR1",
      "doi-asserted-by": "publisher",
      "first-page": "779",
      "DOI": "10.1038/nbt1414",
      "volume": "26",
      "author": "TA Down",
      "year": "2008",
      "unstructured": "Down TA, Rakyan VK, Turner DJ, Flicek P, Li H, Kulesha E, Graf S, Johnson N, Herrero J, Tomazou EM, Thorne NP, Backdahl L, Herberth M, Howe KL, Jackson DK, Miretti MM, Marioni JC, Birney E, Hubbard TJ, Durbin R, Tavare S, Beck S: A Bayesian deconvolution strategy for immunoprecipitation-based DNA methylome analysis. Nat Biotechnol. 2008, 26: 779-785. 10.1038/nbt1414.",
      "journal-title": "Nat Biotechnol"
    },
    {
      "key": "2175_CR2",
      "doi-asserted-by": "publisher",
      "first-page": "1497",
      "DOI": "10.1126/science.1141319",
      "volume": "316",
      "author": "DS Johnson",
      "year": "2007",
      "unstructured": "Johnson DS, Mortazavi A, Myers RM, Wold B: Genome-wide mapping of in vivo protein-DNA interactions. Science. 2007, 316: 1497-1502. 10.1126/science.1141319.",
      "journal-title": "Science"
    },
    {
      "key": "2175_CR3",
      "doi-asserted-by": "publisher",
      "first-page": "1509",
      "DOI": "10.1101/gr.079558.108",
      "volume": "18",
      "author": "JC Marioni",
      "year": "2008",
      "unstructured": "Marioni JC, Mason CE, Mane SM, Stephens M, Gilad Y: RNA-seq: an assessment of technical reproducibility and comparison with gene expression arrays. Genome Res. 2008, 18: 1509-1517. 10.1101/gr.079558.108.",
      "journal-title": "Genome Res"
    },
    {
      "key": "2175_CR4",
      "doi-asserted-by": "publisher",
      "first-page": "53",
      "DOI": "10.1038/nature07517",
      "volume": "456",
      "author": "DR Bentley",
      "year": "2008",
      "unstructured": "Bentley DR, Balasubramanian S, Swerdlow HP, Smith GP, Milton J, Brown CG, Hall KP, Evers DJ, Barnes CL, Bignell HR, Boutell JM, Bryant J, Carter RJ, Keira Cheetham R, Cox AJ, Ellis DJ, Flatbush MR, Gormley NA, Humphray SJ, Irving LJ, Karbelashvili MS, Kirk SM, Li H, Liu X, Maisinger KS, Murray LJ, Obradovic B, Ost T, Parkinson ML, Pratt MR, et al: Accurate whole human genome sequencing using reversible terminator chemistry. Nature. 2008, 456: 53-59. 10.1038/nature07517.",
      "journal-title": "Nature"
    },
    {
      "key": "2175_CR5",
      "doi-asserted-by": "publisher",
      "first-page": "66",
      "DOI": "10.1038/nature07485",
      "volume": "456",
      "author": "TJ Ley",
      "year": "2008",
      "unstructured": "Ley TJ, Mardis ER, Ding L, Fulton B, McLellan MD, Chen K, Dooling D, Dunford-Shore BH, McGrath S, Hickenbotham M, Cook L, Abbott R, Larson DE, Koboldt DC, Pohl C, Smith S, Hawkins A, Abbott S, Locke D, Hillier LW, Miner T, Fulton L, Magrini V, Wylie T, Glasscock J, Conyers J, Sander N, Shi X, Osborne JR, Minx P, et al: DNA sequencing of a cytogenetically normal acute myeloid leukaemia genome. Nature. 2008, 456: 66-72. 10.1038/nature07485.",
      "journal-title": "Nature"
    },
    {
      "key": "2175_CR6",
      "doi-asserted-by": "publisher",
      "first-page": "60",
      "DOI": "10.1038/nature07484",
      "volume": "456",
      "author": "J Wang",
      "year": "2008",
      "unstructured": "Wang J, Wang W, Li R, Li Y, Tian G, Goodman L, Fan W, Zhang J, Li J, Zhang J, Guo Y, Feng B, Li H, Lu Y, Fang X, Liang H, Du Z, Li D, Zhao Y, Hu Y, Yang Z, Zheng H, Hellmann I, Inouye M, Pool J, Yi X, Zhao J, Duan J, Zhou Y, Qin J, et al: The diploid genome sequence of an Asian individual. Nature. 2008, 456: 60-65. 10.1038/nature07484.",
      "journal-title": "Nature"
    },
    {
      "key": "2175_CR7",
      "doi-asserted-by": "publisher",
      "first-page": "1851",
      "DOI": "10.1101/gr.078212.108",
      "volume": "18",
      "author": "H Li",
      "year": "2008",
      "unstructured": "Li H, Ruan J, Durbin R: Mapping short DNA sequencing reads and calling variants using mapping quality scores. Genome Res. 2008, 18: 1851-1858. 10.1101/gr.078212.108.",
      "journal-title": "Genome Res"
    },
    {
      "key": "2175_CR8",
      "doi-asserted-by": "publisher",
      "first-page": "713",
      "DOI": "10.1093/bioinformatics/btn025",
      "volume": "24",
      "author": "R Li",
      "year": "2008",
      "unstructured": "Li R, Li Y, Kristiansen K, Wang J: SOAP: short oligonucleotide alignment program. Bioinformatics. 2008, 24: 713-714. 10.1093/bioinformatics/btn025.",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2175_CR9",
      "doi-asserted-by": "publisher",
      "first-page": "395",
      "DOI": "10.1126/science.319.5862.395",
      "volume": "319",
      "author": "J Kaiser",
      "year": "2008",
      "unstructured": "Kaiser J: DNA sequencing. A plan to capture human diversity in 1000 genomes. Science. 2008, 319: 395-10.1126/science.319.5862.395.",
      "journal-title": "Science"
    },
    {
      "key": "2175_CR10",
      "doi-asserted-by": "publisher",
      "first-page": "128",
      "DOI": "10.1186/1471-2105-9-128",
      "volume": "9",
      "author": "AD Smith",
      "year": "2008",
      "unstructured": "Smith AD, Xuan Z, Zhang MQ: Using quality scores and longer reads improves accuracy of Solexa read mapping. BMC Bioinformatics. 2008, 9: 128-10.1186/1471-2105-9-128.",
      "journal-title": "BMC Bioinformatics"
    },
    {
      "key": "2175_CR11",
      "doi-asserted-by": "publisher",
      "first-page": "2431",
      "DOI": "10.1093/bioinformatics/btn416",
      "volume": "24",
      "author": "H Lin",
      "year": "2008",
      "unstructured": "Lin H, Zhang Z, Zhang MQ, Ma B, Li M: ZOOM! Zillions Of Oligos Mapped. Bioinformatics. 2008, 24: 2431-2437. 10.1093/bioinformatics/btn416.",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2175_CR12",
      "unstructured": "SHRiMP - SHort Read Mapping Package. [http://compbio.cs.toronto.edu/shrimp/]"
    },
    {
      "key": "2175_CR13",
      "doi-asserted-by": "publisher",
      "first-page": "21",
      "DOI": "10.1016/0020-0190(96)00083-X",
      "volume": "59",
      "author": "RA Baeza-Yates",
      "year": "1996",
      "unstructured": "Baeza-Yates RA, Perleberg CH: Fast and practical approximate string matching. Inf Process Lett. 1996, 59: 21-27. 10.1016/0020-0190(96)00083-X.",
      "journal-title": "Inf Process Lett"
    },
    {
      "key": "2175_CR14",
      "first-page": "51",
      "volume": "56",
      "author": "S Burkhardt",
      "year": "2003",
      "unstructured": "Burkhardt S, K\u00e4rkk\u00e4inen J: Better Filtering with Gapped q-Grams. Fundam Inf. 2003, 56: 51-70.",
      "journal-title": "Fundam Inf"
    },
    {
      "key": "2175_CR15",
      "doi-asserted-by": "publisher",
      "first-page": "440",
      "DOI": "10.1093/bioinformatics/18.3.440",
      "volume": "18",
      "author": "B Ma",
      "year": "2002",
      "unstructured": "Ma B, Tromp J, Li M: PatternHunter: faster and more sensitive homology search. Bioinformatics. 2002, 18: 440-445. 10.1093/bioinformatics/18.3.440.",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2175_CR16",
      "doi-asserted-by": "publisher",
      "first-page": "195",
      "DOI": "10.1016/0022-2836(81)90087-5",
      "volume": "147",
      "author": "TF Smith",
      "year": "1981",
      "unstructured": "Smith TF, Waterman MS: Identification of common molecular subsequences. J Mol Biol. 1981, 147: 195-197. 10.1016/0022-2836(81)90087-5.",
      "journal-title": "J Mol Biol"
    },
    {
      "key": "2175_CR17",
      "volume-title": "A Block Sorting Lossless Data Compression Algorithm. Technical Report 124",
      "author": "M Burrows",
      "year": "1994",
      "unstructured": "Burrows M, Wheeler DJ: A Block Sorting Lossless Data Compression Algorithm. Technical Report 124. 1994, Palo Alto, CA: Digital Equipment Corporation"
    },
    {
      "key": "2175_CR18",
      "unstructured": "Ferragina P, Manzini G: Opportunistic data structures with applications. [http://web.unipmn.it/~manzini/papers/focs00draft.pdf]"
    },
    {
      "key": "2175_CR19",
      "first-page": "269",
      "volume-title": "Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete algorithms",
      "author": "P Ferragina",
      "year": "2001",
      "unstructured": "Ferragina P, Manzini G: An experimental study of an opportunistic index. Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete algorithms. 2001, Washington, DC: Society for Industrial and Applied Mathematics, 269-278."
    },
    {
      "key": "2175_CR20",
      "doi-asserted-by": "publisher",
      "first-page": "2306",
      "DOI": "10.1101/gr.1350803",
      "volume": "13",
      "author": "J Healy",
      "year": "2003",
      "unstructured": "Healy J, Thomas EE, Schwartz JT, Wigler M: Annotating large genomes with exact word matches. Genome Res. 2003, 13: 2306-2315. 10.1101/gr.1350803.",
      "journal-title": "Genome Res"
    },
    {
      "key": "2175_CR21",
      "doi-asserted-by": "publisher",
      "first-page": "407",
      "DOI": "10.1089/cmb.2005.12.407",
      "volume": "12",
      "author": "RA Lippert",
      "year": "2005",
      "unstructured": "Lippert RA: Space-efficient whole genome comparisons with Burrows-Wheeler transforms. J Comput Biol. 2005, 12: 407-415. 10.1089/cmb.2005.12.407.",
      "journal-title": "J Comput Biol"
    },
    {
      "key": "2175_CR22",
      "doi-asserted-by": "publisher",
      "first-page": "i195",
      "DOI": "10.1093/bioinformatics/btm200",
      "volume": "23",
      "author": "S Graf",
      "year": "2007",
      "unstructured": "Graf S, Nielsen FG, Kurtz S, Huynen MA, Birney E, Stunnenberg H, Flicek P: Optimized design and assessment of whole genome tiling arrays. Bioinformatics. 2007, 23: i195-i204. 10.1093/bioinformatics/btm200.",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2175_CR23",
      "doi-asserted-by": "publisher",
      "first-page": "791",
      "DOI": "10.1093/bioinformatics/btn032",
      "volume": "24",
      "author": "TW Lam",
      "year": "2008",
      "unstructured": "Lam TW, Sung WK, Tam SL, Wong CK, Yiu SM: Compressed indexing and local alignment of DNA. Bioinformatics. 2008, 24: 791-797. 10.1093/bioinformatics/btn032.",
      "journal-title": "Bioinformatics"
    },
    {
      "key": "2175_CR24",
      "doi-asserted-by": "publisher",
      "first-page": "186",
      "DOI": "10.1101/gr.8.3.186",
      "volume": "8",
      "author": "B Ewing",
      "year": "1998",
      "unstructured": "Ewing B, Green P: Base-calling of automated sequencer traces using phred. II. Error probabilities. Genome Res. 1998, 8: 186-194.",
      "journal-title": "Genome Res"
    },
    {
      "key": "2175_CR25",
      "unstructured": "Bowtie: An ultrafast memory-efficient short read aligner. [http://bowtie.cbcb.umd.edu/]"
    },
    {
      "key": "2175_CR26",
      "doi-asserted-by": "publisher",
      "first-page": "722",
      "DOI": "10.1038/ng.128",
      "volume": "40",
      "author": "PJ Campbell",
      "year": "2008",
      "unstructured": "Campbell PJ, Stephens PJ, Pleasance ED, O'Meara S, Li H, Santarius T, Stebbings LA, Leroy C, Edkins S, Hardy C, Teague JW, Menzies A, Goodhead I, Turner DJ, Clee CM, Quail MA, Cox A, Brown C, Durbin R, Hurles ME, Edwards PA, Bignell GR, Stratton MR, Futreal PA: Identification of somatically acquired rearrangements in cancer using genome-wide massively parallel paired-end sequencing. Nat Genet. 2008, 40: 722-729. 10.1038/ng.128.",
      "journal-title": "Nat Genet"
    },
    {
      "key": "2175_CR27",
      "doi-asserted-by": "publisher",
      "first-page": "987",
      "DOI": "10.1038/ng.195",
      "volume": "40",
      "author": "KE Holt",
      "year": "2008",
      "unstructured": "Holt KE, Parkhill J, Mazzoni CJ, Roumagnac P, Weill FX, Goodhead I, Rance R, Baker S, Maskell DJ, Wain J, Dolecek C, Achtman M, Dougan G: High-throughput sequencing provides insights into genome variation and evolution in Salmonella typhi. Nat Genet. 2008, 40: 987-993. 10.1038/ng.195.",
      "journal-title": "Nat Genet"
    },
    {
      "key": "2175_CR28",
      "doi-asserted-by": "publisher",
      "first-page": "1344",
      "DOI": "10.1126/science.1158441",
      "volume": "320",
      "author": "U Nagalakshmi",
      "year": "2008",
      "unstructured": "Nagalakshmi U, Wang Z, Waern K, Shou C, Raha D, Gerstein M, Snyder M: The transcriptional landscape of the yeast genome defined by RNA sequencing. Science. 2008, 320: 1344-1349. 10.1126/science.1158441.",
      "journal-title": "Science"
    },
    {
      "key": "2175_CR29",
      "doi-asserted-by": "publisher",
      "first-page": "249",
      "DOI": "10.1016/j.tcs.2007.07.018",
      "volume": "387",
      "author": "J K\u00e4rkk\u00e4inen",
      "year": "2007",
      "unstructured": "K\u00e4rkk\u00e4inen J: Fast BWT in small space by blockwise suffix sorting. Theor Comput Sci. 2007, 387: 249-257.",
      "journal-title": "Theor Comput Sci"
    },
    {
      "key": "2175_CR30",
      "doi-asserted-by": "publisher",
      "first-page": "11",
      "DOI": "10.1186/1471-2105-9-11",
      "volume": "9",
      "author": "A Doring",
      "year": "2008",
      "unstructured": "Doring A, Weese D, Rausch T, Reinert K: SeqAn an efficient, generic C++ library for sequence analysis. BMC Bioinformatics. 2008, 9: 11-10.1186/1471-2105-9-11.",
      "journal-title": "BMC Bioinformatics"
    }
  ],
  "container-title": "Genome Biology",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://link.springer.com/content/pdf/10.1186/gb-2009-10-3-r25.pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://link.springer.com/article/10.1186/gb-2009-10-3-r25/fulltext.html",
      "content-type": "text/html",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://link.springer.com/content/pdf/10.1186/gb-2009-10-3-r25.pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2024,
        10,
        8
      ]
    ],
    "date-time": "2024-10-08T10:17:30Z",
    "timestamp": 1728382650000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://genomebiology.biomedcentral.com/articles/10.1186/gb-2009-10-3-r25"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        2009,
        3,
        4
      ]
    ]
  },
  "references-count": 30,
  "journal-issue": {
    "issue": "3",
    "published-online": {
      "date-parts": [
        [
          2009,
          3
        ]
      ]
    }
  },
  "alternative-id": [
    "2175"
  ],
  "URL": "http://dx.doi.org/10.1186/gb-2009-10-3-r25",
  "relation": {},
  "ISSN": [
    "1474-760X"
  ],
  "subject": [],
  "container-title-short": "Genome Biol",
  "published": {
    "date-parts": [
      [
        2009,
        3,
        4
      ]
    ]
  },
  "assertion": [
    {
      "value": "21 October 2008",
      "order": 1,
      "name": "received",
      "label": "Received",
      "group": {
        "name": "ArticleHistory",
        "label": "Article History"
      }
    },
    {
      "value": "19 December 2008",
      "order": 2,
      "name": "revised",
      "label": "Revised",
      "group": {
        "name": "ArticleHistory",
        "label": "Article History"
      }
    },
    {
      "value": "4 March 2009",
      "order": 3,
      "name": "accepted",
      "label": "Accepted",
      "group": {
        "name": "ArticleHistory",
        "label": "Article History"
      }
    },
    {
      "value": "4 March 2009",
      "order": 4,
      "name": "first_online",
      "label": "First Online",
      "group": {
        "name": "ArticleHistory",
        "label": "Article History"
      }
    }
  ],
  "article-number": "R25"
}