An improved approach for reconstructing consensus repeats from short sequence reads
Identifieur interne : 000298 ( Pmc/Corpus ); précédent : 000297; suivant : 000299An improved approach for reconstructing consensus repeats from short sequence reads
Auteurs : Chong Chu ; Jingwen Pei ; Yufeng WuSource :
- BMC Genomics [ 1471-2164 ] ; 2018.
Abstract
Repeat elements are important components of most eukaryotic genomes. Most existing tools for repeat analysis rely either on high quality reference genomes or existing repeat libraries. Thus, it is still challenging to do repeat analysis for species with highly repetitive or complex genomes which often do not have good reference genomes or annotated repeat libraries. Recently we developed a computational method called REPdenovo that constructs consensus repeat sequences directly from short sequence reads, which outperforms an existing tool called RepARK. One major issue with REPdenovo is that it doesn’t perform well for repeats with relatively high divergence rates or low copy numbers. In this paper, we present an improved approach for constructing consensus repeats directly from short reads. Comparing with the original REPdenovo, the improved approach uses more repeat-related k-mers and improves repeat assembly quality using a consensus-based k-mer processing method.
We compare the performance of the new method with REPdenovo and RepARK on Human, Arabidopsis thaliana and Drosophila melanogaster short sequencing data. And the new method fully constructs more repeats in Repbase than the original REPdenovo and RepARK, especially for repeats of higher divergence rates and lower copy number. We also apply our new method on Hummingbird data which doesn’t have a known repeat library, and it constructs many repeat elements that can be validated using PacBio long reads.
We propose an improved method for reconstructing repeat elements directly from short sequence reads. The results show that our new method can assemble more complete repeats than REPdenovo (and also RepARK). Our new approach has been implemented as part of the REPdenovo software package, which is available for download at
Url:
DOI: 10.1186/s12864-018-4920-6
PubMed: 30367582
PubMed Central: 6101065
Links to Exploration step
PMC:6101065Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">An improved approach for reconstructing consensus repeats from short sequence reads</title><author><name sortKey="Chu, Chong" sort="Chu, Chong" uniqKey="Chu C" first="Chong" last="Chu">Chong Chu</name><affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">000000041936754X</institution-id><institution-id institution-id-type="GRID">grid.38142.3c</institution-id><institution>Department of Biomedical Informatics, Harvard Medical School,</institution></institution-wrap>10 Shattuck Street, Boston, 02115 MA USA</nlm:aff></affiliation></author><author><name sortKey="Pei, Jingwen" sort="Pei, Jingwen" uniqKey="Pei J" first="Jingwen" last="Pei">Jingwen Pei</name><affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 0860 4915</institution-id><institution-id institution-id-type="GRID">grid.63054.34</institution-id><institution>Department of Computer Science and Engineering, University of Connecticut,</institution></institution-wrap>371 Fairfield Way, Unit 2155, Storrs, 06269 CT USA</nlm:aff></affiliation></author><author><name sortKey="Wu, Yufeng" sort="Wu, Yufeng" uniqKey="Wu Y" first="Yufeng" last="Wu">Yufeng Wu</name><affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 0860 4915</institution-id><institution-id institution-id-type="GRID">grid.63054.34</institution-id><institution>Department of Computer Science and Engineering, University of Connecticut,</institution></institution-wrap>371 Fairfield Way, Unit 2155, Storrs, 06269 CT USA</nlm:aff></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PMC</idno><idno type="pmid">30367582</idno><idno type="pmc">6101065</idno><idno type="url">http://www.ncbi.nlm.nih.gov/pmc/articles/PMC6101065</idno><idno type="RBID">PMC:6101065</idno><idno type="doi">10.1186/s12864-018-4920-6</idno><date when="2018">2018</date><idno type="wicri:Area/Pmc/Corpus">000298</idno><idno type="wicri:explorRef" wicri:stream="Pmc" wicri:step="Corpus" wicri:corpus="PMC">000298</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a" type="main">An improved approach for reconstructing consensus repeats from short sequence reads</title><author><name sortKey="Chu, Chong" sort="Chu, Chong" uniqKey="Chu C" first="Chong" last="Chu">Chong Chu</name><affiliation><nlm:aff id="Aff1"><institution-wrap><institution-id institution-id-type="ISNI">000000041936754X</institution-id><institution-id institution-id-type="GRID">grid.38142.3c</institution-id><institution>Department of Biomedical Informatics, Harvard Medical School,</institution></institution-wrap>10 Shattuck Street, Boston, 02115 MA USA</nlm:aff></affiliation></author><author><name sortKey="Pei, Jingwen" sort="Pei, Jingwen" uniqKey="Pei J" first="Jingwen" last="Pei">Jingwen Pei</name><affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 0860 4915</institution-id><institution-id institution-id-type="GRID">grid.63054.34</institution-id><institution>Department of Computer Science and Engineering, University of Connecticut,</institution></institution-wrap>371 Fairfield Way, Unit 2155, Storrs, 06269 CT USA</nlm:aff></affiliation></author><author><name sortKey="Wu, Yufeng" sort="Wu, Yufeng" uniqKey="Wu Y" first="Yufeng" last="Wu">Yufeng Wu</name><affiliation><nlm:aff id="Aff2"><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 0860 4915</institution-id><institution-id institution-id-type="GRID">grid.63054.34</institution-id><institution>Department of Computer Science and Engineering, University of Connecticut,</institution></institution-wrap>371 Fairfield Way, Unit 2155, Storrs, 06269 CT USA</nlm:aff></affiliation></author></analytic><series><title level="j">BMC Genomics</title><idno type="eISSN">1471-2164</idno><imprint><date when="2018">2018</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en"><sec><title>Background</title><p>Repeat elements are important components of most eukaryotic genomes. Most existing tools for repeat analysis rely either on high quality reference genomes or existing repeat libraries. Thus, it is still challenging to do repeat analysis for species with highly repetitive or complex genomes which often do not have good reference genomes or annotated repeat libraries. Recently we developed a computational method called REPdenovo that constructs consensus repeat sequences directly from short sequence reads, which outperforms an existing tool called RepARK. One major issue with REPdenovo is that it doesn’t perform well for repeats with relatively high divergence rates or low copy numbers. In this paper, we present an improved approach for constructing consensus repeats directly from short reads. Comparing with the original REPdenovo, the improved approach uses more repeat-related k-mers and improves repeat assembly quality using a consensus-based k-mer processing method.</p></sec><sec><title>Results</title><p>We compare the performance of the new method with REPdenovo and RepARK on Human, Arabidopsis thaliana and Drosophila melanogaster short sequencing data. And the new method fully constructs more repeats in Repbase than the original REPdenovo and RepARK, especially for repeats of higher divergence rates and lower copy number. We also apply our new method on Hummingbird data which doesn’t have a known repeat library, and it constructs many repeat elements that can be validated using PacBio long reads.</p></sec><sec><title>Conclusion</title><p>We propose an improved method for reconstructing repeat elements directly from short sequence reads. The results show that our new method can assemble more complete repeats than REPdenovo (and also RepARK). Our new approach has been implemented as part of the REPdenovo software package, which is available for download at <ext-link ext-link-type="uri" xlink:href="https://github.com/Reedwarbler/REPdenovo">https://github.com/Reedwarbler/REPdenovo</ext-link>.</p></sec></div></front><back><div1 type="bibliography"><listBibl><biblStruct><analytic><author><name sortKey="Jr, Hhk" uniqKey="Jr H">HHK Jr</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Cordaux, R" uniqKey="Cordaux R">R Cordaux</name></author><author><name sortKey="Batzer, Ma" uniqKey="Batzer M">MA Batzer</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Mills, Re" uniqKey="Mills R">RE Mills</name></author><author><name sortKey="Bennett, Ea" uniqKey="Bennett E">EA Bennett</name></author><author><name sortKey="Iskow, Rc" uniqKey="Iskow R">RC Iskow</name></author><author><name sortKey="Devine, Se" uniqKey="Devine S">SE Devine</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Jurka, J" uniqKey="Jurka J">J Jurka</name></author><author><name sortKey="Kapitonov, Vv" uniqKey="Kapitonov V">VV Kapitonov</name></author><author><name sortKey="Pavlicek, A" uniqKey="Pavlicek A">A Pavlicek</name></author><author><name sortKey="Klonowski, P" uniqKey="Klonowski P">P Klonowski</name></author><author><name sortKey="Kohany, O" uniqKey="Kohany O">O Kohany</name></author><author><name sortKey="Walichiewicz, J" uniqKey="Walichiewicz J">J Walichiewicz</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Wheeler, Tj" uniqKey="Wheeler T">TJ Wheeler</name></author><author><name sortKey="Clements, J" uniqKey="Clements J">J Clements</name></author><author><name sortKey="Eddy, Sr" uniqKey="Eddy S">SR Eddy</name></author><author><name sortKey="Hubley, R" uniqKey="Hubley R">R Hubley</name></author><author><name sortKey="Jones, Ta" uniqKey="Jones T">TA Jones</name></author><author><name sortKey="Jurka, J" uniqKey="Jurka J">J Jurka</name></author><author><name sortKey="Smit, Af" uniqKey="Smit A">AF Smit</name></author><author><name sortKey="Finn, Rd" uniqKey="Finn R">RD Finn</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct><analytic><author><name sortKey="Price, Al" uniqKey="Price A">AL Price</name></author><author><name sortKey="Jones, Nc" uniqKey="Jones N">NC Jones</name></author><author><name sortKey="Pevzner, Pa" uniqKey="Pevzner P">PA Pevzner</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Edgar, Rc" uniqKey="Edgar R">RC Edgar</name></author><author><name sortKey="Myers, Ew" uniqKey="Myers E">EW Myers</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Schaeffer, Ce" uniqKey="Schaeffer C">CE Schaeffer</name></author><author><name sortKey="Figueroa, Nd" uniqKey="Figueroa N">ND Figueroa</name></author><author><name sortKey="Liu, X" uniqKey="Liu X">X Liu</name></author><author><name sortKey="Karro, Je" uniqKey="Karro J">JE Karro</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Koch, P" uniqKey="Koch P">P Koch</name></author><author><name sortKey="Platzer, M" uniqKey="Platzer M">M Platzer</name></author><author><name sortKey="Downie, Br" uniqKey="Downie B">BR Downie</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Ye, N" uniqKey="Ye N">N Ye</name></author><author><name sortKey="Zhang, X" uniqKey="Zhang X">X Zhang</name></author><author><name sortKey="Miao, M" uniqKey="Miao M">M Miao</name></author><author><name sortKey="Fan, X" uniqKey="Fan X">X Fan</name></author><author><name sortKey="Zheng, Y" uniqKey="Zheng Y">Y Zheng</name></author><author><name sortKey="Xu, D" uniqKey="Xu D">D Xu</name></author><author><name sortKey="Wang, J" uniqKey="Wang J">J Wang</name></author><author><name sortKey="Zhou, L" uniqKey="Zhou L">L Zhou</name></author><author><name sortKey="Wang, D" uniqKey="Wang D">D Wang</name></author><author><name sortKey="Gao, Y" uniqKey="Gao Y">Y Gao</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Chu, C" uniqKey="Chu C">C Chu</name></author><author><name sortKey="Nielsen, R" uniqKey="Nielsen R">R Nielsen</name></author><author><name sortKey="Wu, Y" uniqKey="Wu Y">Y Wu</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Zerbino, Dr" uniqKey="Zerbino D">DR Zerbino</name></author><author><name sortKey="Birney, E" uniqKey="Birney E">E Birney</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Robinson, Jt" uniqKey="Robinson J">JT Robinson</name></author><author><name sortKey="Thorvaldsd Ttir, H" uniqKey="Thorvaldsd Ttir H">H Thorvaldsdóttir</name></author><author><name sortKey="Winckler, W" uniqKey="Winckler W">W Winckler</name></author><author><name sortKey="Guttman, M" uniqKey="Guttman M">M Guttman</name></author><author><name sortKey="Es Lander, Ea" uniqKey="Es Lander E">ea ES Lander</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Li, H" uniqKey="Li H">H Li</name></author><author><name sortKey="Durbin, R" uniqKey="Durbin R">R Durbin</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Consortium, Gp" uniqKey="Consortium G">GP Consortium</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Chin, C S" uniqKey="Chin C">C-S Chin</name></author><author><name sortKey="Peluso, P" uniqKey="Peluso P">P Peluso</name></author><author><name sortKey="Sedlazeck, Fj" uniqKey="Sedlazeck F">FJ Sedlazeck</name></author><author><name sortKey="Nattestad, M" uniqKey="Nattestad M">M Nattestad</name></author><author><name sortKey="Concepcion, Gt" uniqKey="Concepcion G">GT Concepcion</name></author><author><name sortKey="Clum, A" uniqKey="Clum A">A Clum</name></author><author><name sortKey="Dunn, C" uniqKey="Dunn C">C Dunn</name></author><author><name sortKey="O Alley, R" uniqKey="O Alley R">R O’Malley</name></author><author><name sortKey="Figueroa Balderas, R" uniqKey="Figueroa Balderas R">R Figueroa-Balderas</name></author><author><name sortKey="Morales Cruz, A" uniqKey="Morales Cruz A">A Morales-Cruz</name></author></analytic></biblStruct><biblStruct><analytic><author><name sortKey="Rosenbloom, Kr" uniqKey="Rosenbloom K">KR Rosenbloom</name></author><author><name sortKey="Armstrong, J" uniqKey="Armstrong J">J Armstrong</name></author><author><name sortKey="Barber, Gp" uniqKey="Barber G">GP Barber</name></author><author><name sortKey="Casper, J" uniqKey="Casper J">J Casper</name></author><author><name sortKey="Clawson, H" uniqKey="Clawson H">H Clawson</name></author><author><name sortKey="Diekhans, M" uniqKey="Diekhans M">M Diekhans</name></author><author><name sortKey="Dreszer, Tr" uniqKey="Dreszer T">TR Dreszer</name></author><author><name sortKey="Fujita, Pa" uniqKey="Fujita P">PA Fujita</name></author><author><name sortKey="Guruvadoo, L" uniqKey="Guruvadoo L">L Guruvadoo</name></author><author><name sortKey="Haeussler, M" uniqKey="Haeussler M">M Haeussler</name></author></analytic></biblStruct><biblStruct></biblStruct><biblStruct></biblStruct></listBibl></div1></back></TEI><pmc article-type="research-article"><pmc-dir>properties open_access</pmc-dir>
<front><journal-meta><journal-id journal-id-type="nlm-ta">BMC Genomics</journal-id><journal-id journal-id-type="iso-abbrev">BMC Genomics</journal-id><journal-title-group><journal-title>BMC Genomics</journal-title></journal-title-group><issn pub-type="epub">1471-2164</issn><publisher><publisher-name>BioMed Central</publisher-name><publisher-loc>London</publisher-loc></publisher></journal-meta><article-meta><article-id pub-id-type="pmid">30367582</article-id><article-id pub-id-type="pmc">6101065</article-id><article-id pub-id-type="publisher-id">4920</article-id><article-id pub-id-type="doi">10.1186/s12864-018-4920-6</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research</subject></subj-group></article-categories><title-group><article-title>An improved approach for reconstructing consensus repeats from short sequence reads</article-title></title-group><contrib-group><contrib contrib-type="author"><name><surname>Chu</surname><given-names>Chong</given-names></name><address><email>chong_chu@hms.harvard.edu</email></address><xref ref-type="aff" rid="Aff1">1</xref></contrib><contrib contrib-type="author"><name><surname>Pei</surname><given-names>Jingwen</given-names></name><address><email>jingwen.pei@uconn.edu</email></address><xref ref-type="aff" rid="Aff2">2</xref></contrib><contrib contrib-type="author" corresp="yes"><name><surname>Wu</surname><given-names>Yufeng</given-names></name><address><email>yufeng.wu@uconn.edu</email></address><xref ref-type="aff" rid="Aff2">2</xref></contrib><aff id="Aff1"><label>1</label><institution-wrap><institution-id institution-id-type="ISNI">000000041936754X</institution-id><institution-id institution-id-type="GRID">grid.38142.3c</institution-id><institution>Department of Biomedical Informatics, Harvard Medical School,</institution></institution-wrap>10 Shattuck Street, Boston, 02115 MA USA</aff><aff id="Aff2"><label>2</label><institution-wrap><institution-id institution-id-type="ISNI">0000 0001 0860 4915</institution-id><institution-id institution-id-type="GRID">grid.63054.34</institution-id><institution>Department of Computer Science and Engineering, University of Connecticut,</institution></institution-wrap>371 Fairfield Way, Unit 2155, Storrs, 06269 CT USA</aff></contrib-group><pub-date pub-type="epub"><day>13</day><month>8</month><year>2018</year></pub-date><pub-date pub-type="pmc-release"><day>13</day><month>8</month><year>2018</year></pub-date><pub-date pub-type="collection"><year>2018</year></pub-date><volume>19</volume><issue>Suppl 6</issue><issue-sponsor>Publication of this supplement has not been supported by sponsorship. Information about the source of funding for publication charges can be found in the individual articles. The articles have undergone the journal's standard peer review process for supplements. The Supplement Editors declare that they have no competing interests.</issue-sponsor><elocation-id>566</elocation-id><permissions><copyright-statement>© The Author(s) 2018</copyright-statement><license license-type="OpenAccess"><license-p><bold>Open Access</bold> This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/licenses/by/4.0/">http://creativecommons.org/licenses/by/4.0/</ext-link>), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. The Creative Commons Public Domain Dedication waiver (<ext-link ext-link-type="uri" xlink:href="http://creativecommons.org/publicdomain/zero/1.0/">http://creativecommons.org/publicdomain/zero/1.0/</ext-link>) applies to the data made available in this article, unless otherwise stated.</license-p></license></permissions><abstract id="Abs1"><sec><title>Background</title><p>Repeat elements are important components of most eukaryotic genomes. Most existing tools for repeat analysis rely either on high quality reference genomes or existing repeat libraries. Thus, it is still challenging to do repeat analysis for species with highly repetitive or complex genomes which often do not have good reference genomes or annotated repeat libraries. Recently we developed a computational method called REPdenovo that constructs consensus repeat sequences directly from short sequence reads, which outperforms an existing tool called RepARK. One major issue with REPdenovo is that it doesn’t perform well for repeats with relatively high divergence rates or low copy numbers. In this paper, we present an improved approach for constructing consensus repeats directly from short reads. Comparing with the original REPdenovo, the improved approach uses more repeat-related k-mers and improves repeat assembly quality using a consensus-based k-mer processing method.</p></sec><sec><title>Results</title><p>We compare the performance of the new method with REPdenovo and RepARK on Human, Arabidopsis thaliana and Drosophila melanogaster short sequencing data. And the new method fully constructs more repeats in Repbase than the original REPdenovo and RepARK, especially for repeats of higher divergence rates and lower copy number. We also apply our new method on Hummingbird data which doesn’t have a known repeat library, and it constructs many repeat elements that can be validated using PacBio long reads.</p></sec><sec><title>Conclusion</title><p>We propose an improved method for reconstructing repeat elements directly from short sequence reads. The results show that our new method can assemble more complete repeats than REPdenovo (and also RepARK). Our new approach has been implemented as part of the REPdenovo software package, which is available for download at <ext-link ext-link-type="uri" xlink:href="https://github.com/Reedwarbler/REPdenovo">https://github.com/Reedwarbler/REPdenovo</ext-link>.</p></sec></abstract><kwd-group xml:lang="en"><title>Keywords</title><kwd>Repeat elements</kwd><kwd>De novo genome assembly</kwd><kwd>Sequence analysis</kwd></kwd-group><conference><conf-name>13th International Symposium on Bioinformatics Research and Applications (ISBRA 2017)</conf-name><conf-loc>Honolulu, Hawaii, USA</conf-loc><conf-date>30 May - 2 June 2017</conf-date></conference><custom-meta-group><custom-meta><meta-name>issue-copyright-statement</meta-name><meta-value>© The Author(s) 2018</meta-value></custom-meta></custom-meta-group></article-meta></front><body><sec id="Sec1"><title>Background</title><p>A repeat is one segment of DNA that appears multiple times in the genome in identical or near-identical form. There are many types of repeats such as transposable elements (TEs), tandem repeats, satellite repeats, and simple repeats [<xref ref-type="bibr" rid="CR1">1</xref>, <xref ref-type="bibr" rid="CR2">2</xref>]. Among these, TEs are perhaps the most well-known. TEs can amplify themselves in the genome using various mechanisms, typically involving RNA intermediates. TEs are believed to constitute 25% to 40% of most mammalian genomes [<xref ref-type="bibr" rid="CR1">1</xref>, <xref ref-type="bibr" rid="CR2">2</xref>]. In humans, the most common TEs are Long Interspersed Elements (LINE-1s or L1s), Short Interspersed Element (SINEs), and Long Terminal Repeats (LTRs), comprising approximately 17%, 11% and 8% of the human genome, respectively. While most of the TEs in humans are inactive now, some including Alus, SVA, L1, and possibly HERV-K are believed to be still active [<xref ref-type="bibr" rid="CR3">3</xref>].</p><p>Many computational approaches have been developed for repeat analysis. The most commonly used tools are those based on curated repeat libraries such as Repbase [<xref ref-type="bibr" rid="CR4">4</xref>] and Dfam [<xref ref-type="bibr" rid="CR5">5</xref>]. RepeatMasker [<xref ref-type="bibr" rid="CR6">6</xref>] is the most widely used tool of this type. It aligns genomic sequences to known consensus repeat sequences to mask or annotate the genomic sequences. There are also tools designed for constructing repeat libraries from reference genomes. RepeatScout [<xref ref-type="bibr" rid="CR7">7</xref>], PILER [<xref ref-type="bibr" rid="CR8">8</xref>] and phRAIDER [<xref ref-type="bibr" rid="CR9">9</xref>] all belong to this type. One limitation of these tools is that they all either require the reference genome or an existing repeat library to call or analyze repeats. However, for complex (e.g. highly repetitive) genomes or genomes from some recently sequenced species, there are only low quality assembled genomes available and often no existing annotated repeat libraries. Thus, it is useful to develop tools for analyzing repeats directly from short reads, without the need for either reference genomes or repeat library. RepARK [<xref ref-type="bibr" rid="CR10">10</xref>] is one such tool. It first runs k-mer counting and isolates highly frequent k-mers. It then assembles the highly frequent k-mers to construct the repeats. RepARK has been used to construct repeats in recent publications (see e.g. [<xref ref-type="bibr" rid="CR11">11</xref>]). One major disadvantage of RepARK is that most constructed repeats are fragmented or just pieces of the whole repeats. Recently, we developed REPdenovo [<xref ref-type="bibr" rid="CR12">12</xref>], a computational approach for constructing repeats directly from short sequence reads. Comparing to RepARK, REPdenovo not only constructs more repeats, but also generates more complete (i.e. longer) repeats. However, REPdenovo doesn’t work well for highly divergent or low copy number repeats.</p><p>In the paper, we propose an improved method for reconstructing repeat elements from short reads. Similar to the original REPdenovo, our new method also finds and assembles these highly frequent k-mers to form consensus repeat sequences. Here are the two main improvements over the original REPdenovo:
<list list-type="bullet"><list-item><p>Our new method uses more repeat-related k-mers than the original REPdenovo for repeat assembly, and can assemble longer consensus repeats.</p></list-item><list-item><p>Our new method runs a randomized algorithm to generate more accurate consensus k-mers than the original REPdenovo. This improves the quality of the assembled repeats.</p></list-item></list></p><p>Comparing to the original REPdenovo and RepARK, our new method can construct more fully assembled repeats in Repbase on both Human, Arabidopsis and Drosophila data, especially for higher divergent, lower copy number and longer repeats. We also apply the new method on Hummingbird data, which has no existing repeat library. Most of the repeats constructed by our new method for Hummingbird can be fully aligned to PacBio long reads. Many of these repeats are long. More than half of the Hummingbird repeats are masked by RepeatMasker, which suggests that our assembly works well. Moreover, many of the assembled repeats are likely to be novel because there are no matches in RepBase, which suggests these may be present in only Hummingbird or its close related species.</p></sec><sec id="Sec2"><title>Method</title><p>Similar to the original REPdenovo, our new method assembles consensus repeats directly from sequence reads. The high-level procedure is shown in Fig. <xref rid="Fig1" ref-type="fig">1</xref>. In the following, we first provide a brief description on the repeat assembly procedure with frequent k-mers that is used by the original REPdenovo. We then illustrate the key technical problems that make the original REPdenovo perform poorly on highly divergent and low copy number repeats. We present two approaches that are implemented by our new method. These approaches allow better construction of highly divergent or low copy number repeats.
<fig id="Fig1"><label>Fig. 1</label><caption><p>High-level procedure of improved repeat construction. Thick bars: genomic sequences. Yellow thick bars: repeat copies. Colored squares within thick bars: mutations (substitutions and indels) within repeats. Thin bars: k-mers. There are six main steps. <bold>a</bold> K-mer counting for the reads. <bold>b</bold> Find the highly frequent k-mers and k-mers with intermediate frequencies according to a user-specified cutoff on k-mer frequency. <bold>c</bold> Find repeat-related k-mers by aligning those k-mers of intermediate frequencies to highly frequent k-mers. <bold>d</bold> Improve k-mer quality with a consensus-based approach. <bold>e</bold> Assemble the improved k-mers. <bold>f</bold> Merge contigs that have reliable prefix-suffix overlap</p></caption><graphic xlink:href="12864_2018_4920_Fig1_HTML" id="MO1"></graphic></fig></p><sec id="Sec3"><title>Repeat assembly from frequent k-mers</title><p>For completeness, we provide a brief introduction on repeat assembly from frequent k-mers. Repeats usually have many copies in the genome. For low divergent and high copy number repeats, k-mers generated from copies of the same repeat at the same position will be identical with high probability. Thus the frequencies of such k-mers will be higher than those of k-mers from non-repetitive regions. Thus, with given cutoff (say <italic>n</italic> times of the average k-mer frequency, where <italic>n</italic> can be viewed as the copy number), these highly frequent k-mers from repeats can be identified, while the less frequent k-mers will be discarded since they are unlikely to come from repeats. Now if we view the repeats as “genomes” and the frequent k-mers are the “reads” as in genome assembly, the repeats can be assembled from these frequent k-mers using standard genome assembly tools such as Velvet [<xref ref-type="bibr" rid="CR13">13</xref>]. This is the key observation of RepARK and the original REPdenovo. However, in practice complete consensus repeat sequences can rarely be assembled in this way. This is because the variations on repeat copies and also read errors make the repeat copies divergent from the consensus. As the result, even for low divergent repeats, usually only short contigs can be directly assembled. Figure <xref rid="Fig2" ref-type="fig">2</xref>b shows one such situation. The improvement made by the original REPdenovo is that it performs a second-round assembly: it tries to assemble short contigs to form longer consensus repeats based on reliable prefix-suffix matches of the contigs. Refer to [<xref ref-type="bibr" rid="CR12">12</xref>] for more details.
<fig id="Fig2"><label>Fig. 2</label><caption><p>Illustration of two example repeats that are not fully constructed by the original REPdenovo. Highly frequent 30-mers of one human individual NA19230 are aligned to the human consensus repeats in Repbase. The left part (<bold>a</bold>) shows the alignments on repeat “LTR2B”. Two gaps are formed when 30-mers originated from highly divergent regions have low frequencies due to repeat copy divergence. The right part (<bold>b</bold>) shows the alignments on repeat “LTR10C”. The colored bars are variations on copies. The assembled contigs are fragmented because the 30-mers are of highly divergence</p></caption><graphic xlink:href="12864_2018_4920_Fig2_HTML" id="MO2"></graphic></fig></p></sec><sec id="Sec4"><title>The difficulty of assembling highly divergent repeat regions</title><p>The main problem with the original REPdenovo is that it cannot fully assemble highly divergent or low copy repeats. Even when a long repeat is overall of low divergence, there may still be regions with high divergence rate. In this case, the original REPdenovo also cannot assemble the high divergent regions within a repeat. There are two reasons. First, when the repeat divergence rate is high or the copy number is low for a region, k-mers originated from the this region will likely be of low frequency and thus are discarded. As a result, when repeat assembly is performed, only fragments of repeats will be obtained since k-mers from the highly divergent regions are missing. Moreover, even though some k-mers from highly divergent regions are present in repeat assembly, it is still challenging to assemble whole repeats. This is because contigs may break at regions with sequence variations. In Fig. <xref rid="Fig2" ref-type="fig">2</xref> we show two examples to illustrate these two issues. First, we obtain highly frequent (at 10 times of the average k-mer frequency) 30-mers from real reads of one human individual NA19239. Then we align these 30-mers to the human consensus repeats released in Repbase. Two alignment cases on repeats “LTR2B” and “LTR10C” are shown in Fig. <xref rid="Fig2" ref-type="fig">2</xref> through IGV [<xref ref-type="bibr" rid="CR14">14</xref>]. The left alignment is for “LTR2B” with length 490bp. Apparently, there are two gaps with very low or no k-mer mapped, which will cause the assembly of this repeat to have at least 3 segments. The right alignment is for “LTR10C” which has more variations (the colored bars). When there are variations, genome assemblers e.g. Velvet [<xref ref-type="bibr" rid="CR13">13</xref>] usually construct contigs that are short and fragmented.</p><p>In order to assemble repeats with higher divergence rates, we need to find more repeat-related k-mers that originate from highly divergent repeat regions. In the following, we first describe a new method for finding such less frequent repeat-related k-mers. We then use these repeat-related k-mers to improve the quality of the assembled repeats.</p></sec><sec id="Sec5"><title>Mapping-based alignment for finding more repeat-related k-mers</title><p>We now focus on assembling repeats that have higher divergences and/or lower copy numbers than those constructed by the original REPdenovo. Many k-mers from highly divergent regions may have relatively low frequencies. These k-mers are then discarded and are not included for repeat assembly. A main observation is that these discarded repeat-related k-mers usually have high sequence identity with some repeat-related k-mers with high-frequency. Recall that k-mers with high frequencies are likely to come from some repeats. Thus, if a k-mer is similar to some highly frequent k-mer, this is an indication that this k-mer is also related to some repeat. Therefore, we can compare the sequences of all the discarded k-mers with the highly frequent k-mers. If a discarded k-mer has reliable prefix-suffix match with some highly frequent k-mer, this k-mer should be kept for repeat assembly. However, direct comparison of all pairs of lower frequency and high-frequent k-mers using dynamic programming is infeasible empirically. This is because the number of lower frequency k-mers can be very large (usually in millions), and there can also be many highly frequent k-mers.</p><p>To develop a practical method, we take the following “mapping-based alignment” approach. The key idea is creating a “reference k-mer genome” by concatenating all the high-frequent k-mers. We then view the less frequent k-mers as “reads”. The reads mapping tool BWA [<xref ref-type="bibr" rid="CR15">15</xref>] is used to align these “reads” to the reference k-mer genome. The mapped k-mers are kept for repeat assembly. This is shown in step (c) of Fig. <xref rid="Fig1" ref-type="fig">1</xref>. This approach works because we only want to find k-mers that have high sequence similarity with some high-frequent k-mers. Our experience shows that reads mapping tools work well for this purpose. The main benefit of mapping-based alignment is that it allows small insertions and deletions, and thus can find more repeat-related k-mers. We only consider the lower frequency k-mers that are of intermediate frequency (by default three times or more over the read depth). This not only speeds up the computation and also reduces false positives. This is because k-mers from highly divergent parts of repeats still tend to have frequencies higher than average. BWA “mem” is used with option “-T” to set the minimum score for the alignments. Since we want to avoid false positives, we use no penalty for mismatch, gap open, gap extension and mismatch, and set <italic>k</italic>−5 as the minimum score by default for reads mapping. This step can be performed iteratively if users want to construct more fully constructed repeats. Note that this step may introduce some unrelated k-mers and lead to false positives in repeat assembly. Thus, there is a trade-off in determining how many times this step is run. The mapped k-mers are merged with the highly frequent k-mers and are used as input of the next step.</p></sec><sec id="Sec6"><title>K-mer polishing</title><p>As illustrated in Fig. <xref rid="Fig2" ref-type="fig">2</xref>b, k-mers from repeat copies with variations can often only be assembled to form short contigs. If there are only mismatches on the two k-mers from the same position of two repeat copies, most positions of the two k-mers are still the same. We call these two k-mers “end-to-end” matched. Now suppose there is a single inserted (or deleted) base at the beginning of a k-mer. Then k-mers started from the insertion (or deletion) will be “end-to-end” matched with the k-mer from the other copy that is one base left (or right). “End-to-end” match can be used to generate the consensus k-mers. Consensus k-mers can be more reliable to use for repeat assembly for highly divergent repeats.</p><p>Given the merged k-mers (highly frequent and also the mapped intermediate frequent k-mers) generated by mapping-based alignment, a randomized algorithm is used to generate the “end-to-end” matches. For two k-mers with length <italic>k</italic>, we randomly pick <italic>h</italic> bases from the same positions of the two k-mers. If the chosen h-mers are the same, then the two k-mers will be considered as “end-to-end” matched. This procedure runs for <italic>n</italic> times to guarantee the two “end-to-end” matched k-mers are grouped together. Here, we require at least one match between the two h-mers out of <italic>n</italic> times to group the two k-mers. Given the values for <italic>n</italic>,<italic>k</italic>,<italic>h</italic>, the probability <italic>p</italic> of two k-mers being grouped is:
<disp-formula id="Equa"><alternatives><tex-math id="M1">\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document} $$p=1- (1-\frac{\binom{k-e}{h}}{\binom{k}{h}})^{n} $$ \end{document}</tex-math><mml:math id="M2"><mml:mrow><mml:mi>p</mml:mi><mml:mo>=</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:msup><mml:mrow><mml:mo>(</mml:mo><mml:mn>1</mml:mn><mml:mo>−</mml:mo><mml:mfrac><mml:mrow><mml:mfenced close=")" open="(" separators=""><mml:mfrac linethickness="0.0pt"><mml:mrow><mml:mi>k</mml:mi><mml:mo>−</mml:mo><mml:mi>e</mml:mi></mml:mrow><mml:mrow><mml:mi>h</mml:mi></mml:mrow></mml:mfrac></mml:mfenced></mml:mrow><mml:mrow><mml:mfenced close=")" open="(" separators=""><mml:mfrac linethickness="0.0pt"><mml:mrow><mml:mi>k</mml:mi></mml:mrow><mml:mrow><mml:mi>h</mml:mi></mml:mrow></mml:mfrac></mml:mfenced></mml:mrow></mml:mfrac><mml:mo>)</mml:mo></mml:mrow><mml:mrow><mml:mi>n</mml:mi></mml:mrow></mml:msup></mml:mrow></mml:math><graphic xlink:href="12864_2018_4920_Article_Equa.gif" position="anchor"></graphic></alternatives></disp-formula> Here <italic>e</italic> is the allowed edit distance between two “end-to-end” matched k-mers. By default, the value of <italic>e</italic> is set to 1, that is, we allow one mismatch, insertion or deletion in one k-mer. This is reasonable because usually <italic>k</italic> is not large (less than 100).</p><p>When matched k-mers are found, we use a weighted voting method for constructing the consensus k-mer. For each position, each k-mer votes for one of the four possible bases with weight <italic>f</italic>, where <italic>f</italic> is the frequency of the k-mer. The base with maximum votes is chosen as the base at that position. The maximum vote out of all positions is considered as the final frequency of the consensus k-mer. This step is implemented in the popular map-reduce way for efficient processing: first we partition the k-mer file into several parts, and then run the polishing step for each part. Finally we merge the results of each partition.</p></sec></sec><sec id="Sec7"><title>Results and discussion</title><p>To evaluate the performance of the new method, we compare it against the original REPdenovo and RepARK on Human, Arabidopsis thaliana, and Drosophila melanogaster data. These thress species are well studied and have good quality of annotation, which can provide benchmark for our comparison. We use the repeat libraries of these three species released in Repbase [<xref ref-type="bibr" rid="CR4">4</xref>] as the benchmark. Short sequence reads of one human individual NA19239 from the 1000 Genomes Project [<xref ref-type="bibr" rid="CR16">16</xref>] is used. The read depth is around 6X with read length 100bp. For Arabidopsis thaliana, the F1 sample released in [<xref ref-type="bibr" rid="CR17">17</xref>] is used with read depth 10X and read length 250bp. And the Drosophila melanogaster data is downloaded from NCBI (accession number SRR3939094) with read length 151bp and read depth 120X. We compare the divergence rate, copy number and repeat length of the constructed repeat elements. To get the divergence rate and copy number of repeats, we use UCSC annotations [<xref ref-type="bibr" rid="CR18">18</xref>], which utilizes copy numbers generated by RepeatMasker. We also apply the new method to infer the repeat elements of Hummingbird. There is no existing repeat library for Hummingbird, but there are recently sequenced PacBio long reads [<xref ref-type="bibr" rid="CR19">19</xref>] which can be used to validate the constructed repeats. For Hummingbird, we use the short sequence reads released in the GeneBank (accession number SRR943146), where the average coverage is around 20X with read length 101bp.</p><sec id="Sec8"><title>Comparison with Human, Arabidopsis thaliana and Drosaphila melanogaster data</title><p>We evaluate the performance of the two versions of REPdenovo and RepARK by comparing the assembled repeats from these tools with the consensus repeats released in Repbase. There are 1,119, 525 and 238 consensus repeats for Human, Arabidopsis thaliana and Drosaphila melanogaster respectively. In the following, “hits” refers to constructed repeats that are present in Repbase. We use the following metrics previously used in [<xref ref-type="bibr" rid="CR12">12</xref>] to compare the two versions of REPdenovo to RepARK:
<list list-type="order"><list-item><p>The number of Repbase hits with > 85% sequence identity across the length of the Repbase consensus repeat sequence.</p></list-item><list-item><p>Average Repbase coverage. For a Repbase hit, this is the average fraction of the Repbase repeat covered by the assembled sequence. We use the set of non-overlapping assembled repeats that achieve the largest coverage.</p></list-item><list-item><p>Average Repbase coverage by the longest assembled repeat. One repeat in Repbase may be covered by several constructed repeats. When calculating the average coverage, we choose the longest one.</p></list-item></list></p><p>In Table <xref rid="Tab1" ref-type="table">1</xref> we show the detailed comparison of the three methods on Human, Arabidopsis thaliana and Drosaphila melanogaster data. Besides the three metrics, we also show the number of repeats in Repbase that are partially (no identity threshold requirement) constructed. The results show that both versions of REPdenovo outperform RepARK on both the number of hit Repbase repeats and the average covered repeat length. In comparison, the original REPdenovo fully constructs 89 (out of the 220 hits), 11 (out of the 68 hits) and 32 (out of the 133 hits) repeats in Repbase for human, Arabidopsis and Drosaphila respectively. And the new version of REPdenovo fully reconstructs 108 (out of the 332 hits), 24 (out of the 102 hits) and 69 (out of the 177 hits) repeats in Repbase for Human, Arabidopsis and Drosaphila respectively. Therefore, our new method significantly outperforms the original REPdenovo in terms of the number of fully constructed repeats.
<table-wrap id="Tab1"><label>Table 1</label><caption><p>Comparison between the two versions of REPdenovo and RepARK on Human, Arabidopsis thaliana, and Drosophila melanogaster data</p></caption><table frame="hsides" rules="groups"><thead><tr><th align="left">Species</th><th align="left">Methods</th><th align="left"><italic>N</italic></th><th align="left"><italic>N</italic><sub><italic>h</italic></sub></th><th align="left"><italic>N</italic><sub>0</sub></th><th align="left"><italic>C</italic><sub><italic>avg</italic></sub></th><th align="left"><italic>C</italic><sub><italic>m</italic></sub></th></tr></thead><tbody><tr><td align="left"></td><td align="left">REPdenovo*</td><td align="left">6192</td><td align="left">108</td><td align="left">332</td><td align="left">0.61</td><td align="left">0.49</td></tr><tr><td align="left"></td><td align="left">REPdenovo</td><td align="left">4648</td><td align="left">89</td><td align="left">220</td><td align="left">0.66</td><td align="left">0.55</td></tr><tr><td align="left">Human</td><td align="left">RepARK</td><td align="left">2046</td><td align="left">1</td><td align="left">168</td><td align="left">0.34</td><td align="left">0.21</td></tr><tr><td align="left"></td><td align="left">REPdenovo*</td><td align="left">808</td><td align="left">24</td><td align="left">102</td><td align="left">0.42</td><td align="left">0.31</td></tr><tr><td align="left"></td><td align="left">REPdenovo</td><td align="left">508</td><td align="left">11</td><td align="left">68</td><td align="left">0.46</td><td align="left">0.34</td></tr><tr><td align="left">Arabidopsis</td><td align="left">RepARK</td><td align="left">632</td><td align="left">8</td><td align="left">59</td><td align="left">0.33</td><td align="left">0.21</td></tr><tr><td align="left"></td><td align="left">REPdenovo*</td><td align="left">3644</td><td align="left">69</td><td align="left">177</td><td align="left">0.83</td><td align="left">0.61</td></tr><tr><td align="left"></td><td align="left">REPdenovo</td><td align="left">3031</td><td align="left">33</td><td align="left">133</td><td align="left">0.67</td><td align="left">0.49</td></tr><tr><td align="left">Drosophila</td><td align="left">RepARK</td><td align="left">2,787</td><td align="left">26</td><td align="left">133</td><td align="left">0.66</td><td align="left">0.44</td></tr></tbody></table><table-wrap-foot><p>REPdenovo*: the new method. N: the total number of repeats constructed. <italic>N</italic><sub><italic>h</italic></sub> and <italic>N</italic><sub>0</sub> are the number of hit Repbase repeats with at least 85% and 0% similarity respectively. <italic>C</italic><sub><italic>avg</italic></sub>: the average Repbase coverage which indicates the average percent of a repeat in Repbase is covered by the constructed repeats. <italic>C</italic><sub><italic>m</italic></sub>: the average Repbase coverage by the longest assembled repeat</p></table-wrap-foot></table-wrap></p><p>Note that for Human and Arabidopsis results, the <italic>C</italic><sub><italic>avg</italic></sub> and <italic>C</italic><sub><italic>m</italic></sub> values for the original REPdenovo are slightly larger than the improved version. This is mainly because the new method reports much more repeats than the original REPdenovo. Our experience shows that the new method tends to construct copies of the same repeat with different variations and thus construct more repeats in general than the original REPdenovo. We provide more information in the Conclusions section.</p></sec><sec id="Sec9"><title>Comparison between the two versions of REPdenovo</title><p>In Section “<xref rid="Sec2" ref-type="sec">Method</xref>” we show the new method can find more k-mers originated from the repeat regions than the original REPdenovo. As a result, it can construct not only higher diverged regions, but also less frequent repeat elements than the original REPdenovo. As shown in Fig. <xref rid="Fig3" ref-type="fig">3</xref>, there are a number of low divergent but low copy number repeats that are only constructed by our new method.
<fig id="Fig3"><label>Fig. 3</label><caption><p>Comparison of the fully constructed repeats in Repbase for the two version of REPdenovo. Bullet circles: hit Repbase repeats constructed by both versions of REPdenovo. Empty circles: hit Repbase repeats constructed only by the new version. Figure in the right-up corner is zoomed in the red rectangle region. There are 154(out of all the 220) bullet circles and 57 empty circles. Most of these 57 ones fall in higher divergent and lower copy number regions (the regions of blue rectangles)</p></caption><graphic xlink:href="12864_2018_4920_Fig3_HTML" id="MO3"></graphic></fig></p><p>In Fig. <xref rid="Fig3" ref-type="fig">3</xref>, we show the comparison between the two versions of REPdenovo on the divergence rate and copy number of the constructed repeats. The bullet circle points are the repeats constructed by both versions, while the empty circle points are the repeats only constructed by the new method. Note that 211 repeats (out of the 332 repeats) are shown in the figure. This is because out of the 332 repeats only 211 can find the divergence rate and copy number information from the UCSC annotations (mainly because the IDs do not match between Repbase and RepeatMasker). The results show that most of the repeats only constructed by the new method have higher divergence rates and are less frequent.</p></sec><sec id="Sec10"><title>Repeat elements construction for Hummingbird</title><p>Our new method can be used to construct repeat elements for species that have no existing repeat libraries or no high quality reference genomes. We apply our new method on the Hummingbird data. 2406 repeats are constructed. Because there is no existing repeat library of Hummingbird to compare with, we cannot directly validate the constructed repeats. Generally, long reads are long enough to cover most of the repeats which provides a way to check whether the assembled repeats are real. Thus, we run NCIB Blast on the constructed repeats to the error-corrected PacBio long reads of Hummingbird. Out of the 2406 repeats, 1617 are almost fully aligned (with similarity larger than 85%). Among these, 1406 are perfectly fully aligned. This indicates that most of the constructed repeats are likely to be real. In Fig. <xref rid="Fig4" ref-type="fig">4</xref> we show the length distribution of the 1617 constructed repeats. Most of the repeats are shorter than 1500bp. There are 64 repeats longer than 2000bp.
<fig id="Fig4"><label>Fig. 4</label><caption><p>Length distribution of the selected constructed Hummingbird repeats</p></caption><graphic xlink:href="12864_2018_4920_Fig4_HTML" id="MO4"></graphic></fig></p><p>To further analyze the constructed repeats, we run RepeatMasker on the 1,617 repeats. In general, RepeatMasker relies on an external repeat library to mask the repeats, which means it will not work for Hummingbird which has no existing repeat library. However, homologous copies of repeats usually exist in multiple species. In this study, we use the “Vertebrate (Other than below)” from RepeatMasker as the DNA source to mask the constructed repeats. Out of the 1,617 repeats 928 are masked and the rest 628 ones are unmasked. Detailed information are shown in Table <xref rid="Tab2" ref-type="table">2</xref>. Note that one repeat may have several regions and the regions may be of different repeat families. Thus one repeat may be reported for several times with different regions and repeat families. For the statistic in Table <xref rid="Tab2" ref-type="table">2</xref>, the row marked as “Unique” only counts those repeats with one unique masked repeat family, while the row marked as “Dup.” allows one repeat counted for more than once. Many of the repeats are masked as “LINE”, which is supported by the known fact that “LINE” repeats widely exist in vertebrate. We believe the 628 unmasked repeats are possibly Hummingbird-only or its close relatives, because they are of high frequency and fully aligned to long reads but have no hits on the “Vertebrate” general library.
<table-wrap id="Tab2"><label>Table 2</label><caption><p>Masking information of the 1617 long reads validated Hummingbird repeats</p></caption><table frame="hsides" rules="groups"><thead><tr><th align="left">Category</th><th align="left">LINE</th><th align="left">SINE</th><th align="left">LTR</th><th align="left">Retroposon</th><th align="left">Satellite</th><th align="left">Simple_repeat</th><th align="left">Low_complexity</th><th align="left">rRNA</th><th align="left">Other</th></tr></thead><tbody><tr><td align="left">Unique</td><td align="left">371</td><td align="left">0</td><td align="left">139</td><td align="left">0</td><td align="left">10</td><td align="left">98</td><td align="left">31</td><td align="left">0</td><td align="left">5</td></tr><tr><td align="left">Dup.</td><td align="left">557</td><td align="left">6</td><td align="left">244</td><td align="left">0</td><td align="left">19</td><td align="left">216</td><td align="left">52</td><td align="left">1</td><td align="left">81</td></tr></tbody></table><table-wrap-foot><p>For one repeat, RepeatMasker may report several hits depending on whether the repeat is composed of regions of different repeat types. “Unique” only counts those repeats with one unique masked repeat family, while “Dup.” allows one repeat counted more than once</p></table-wrap-foot></table-wrap></p></sec></sec><sec id="Sec11" sec-type="conclusion"><title>Conclusion</title><p>In this paper, we propose an improved method for reconstructing repeat elements directly from short sequence reads. Our new method is able to collect more repeat-related k-mers. Results on both Human, Arabidopsis and Drosaphila data show that the new method can fully construct more repeats in Repbase than the original REPdenovo and RepARK, especially for repeats of higher divergence rates and lower copy number. In Fig. <xref rid="Fig5" ref-type="fig">5</xref>, we show the comparison of the two versions of REPdenovo on constructing one sample repeat “LTR2B”, which is mentioned in section <xref rid="Fig3" ref-type="fig">3</xref>. The original REPdenovo generates three pieces of the repeat, while the new version constructs the whole repeat.
<fig id="Fig5"><label>Fig. 5</label><caption><p>Comparison between the two versions of REPdenovo on constructing one sample repeat “LTR2B”. The old version generates three pieces of the repeat, while the new version constructs the whole repeat</p></caption><graphic xlink:href="12864_2018_4920_Fig5_HTML" id="MO5"></graphic></fig></p><p>We also apply the new method on Hummingbird data and assemble 1,619 repeats that can be validated from PacBio long reads. Many of these repeats are likely to be novel (i.e. previously not present in RepBase). We note that long sequence reads (e.g. PacBio reads) may provide new data for repeat analysis. We believe that our method can still be useful for repeat analysis especially for longer repeats even when long reads are available. For example, our method assembles 64 Hummingbird repeats that are longer than 2,000 bp, which can be difficult to analyze even with long reads.</p><p>The new method reports more repeats than the original REPdenovo. There are two main reasons for this increase. First, many repeats are of high divergence rate and many constructed contigs are just fragments of one repeat. As more repeat-related k-mers are used in assembly, many previously uncovered regions are constructed, although many are just fragments of the repeat. The other source of more repeats by the new method is that many repeats are just copies of the same repeat consensus. To evaluate how many constructed repeats are from the same repeat consensus, we design the following copy cluster algorithm: First, we check the pairwise similarity between each two repeats, and if the similarity is larger then threshold (by default 0.85), we view the two repeats are of the same group. Then a union find set algorithm is used to cluster the repeats. We apply the clustering on the 6,192 constructed repeats of human individual NA19239, and 3,196 groups are reported. Therefore, the number of constructed repeats can be greatly reduced when related copies are removed.</p></sec></body><back><ack><title>Acknowledgements</title><p>The abridged abstract of this work was previously published in the Proceedings of the 13th International Symposium on Bioinformatics Research and Applications (ISBRA 2017), Lecture Notes in Computer Science: Bioinformatics Research and Applications [<xref ref-type="bibr" rid="CR20">20</xref>].</p><sec id="d29e1086"><title>Funding</title><p>This research is supported in part by grants IIS-0953563, IIS-1447711 and IIS-1526415 from National Science Foundation. And the publication of the paper is charged from NSF grant IIS-1526415.</p></sec><sec id="d29e1091" sec-type="data-availability"><title>Availability of data and materials</title><p>All data generated or analysed during this study are included in this published article.</p></sec><sec id="d29e1096"><title>About this supplement</title><p>This article has been published as part of <italic>BMC Genomics</italic> Volume 19 Supplement 6, 2018: Selected articles from the 13th International Symposium on Bioinformatics Research and Applications (ISBRA 2017): genomics. The full contents of the supplement are available online at <ext-link ext-link-type="uri" xlink:href="https://bmcgenomics.biomedcentral.com/articles/supplements/volume-19-supplement-6">https://bmcgenomics.biomedcentral.com/articles/supplements/volume-19-supplement-6</ext-link>.</p></sec></ack><notes notes-type="author-contribution"><title>Authors’ contributions</title><p>CC designed algorithms, developed software, performed analysis and experiments, and wrote the paper. JP performed analysis and experiments. YW designed the algorithms, wrote the paper and supervised the project. All authors have read and approved the final manuscript.</p></notes><notes notes-type="COI-statement"><sec><title>Ethics approval and consent to participate</title><p>Not applicable.</p></sec><sec><title>Consent for publication</title><p>Not applicable.</p></sec><sec><title>Competing interests</title><p>The authors declare that they have no competing interests.</p></sec><sec><title>Publisher’s Note</title><p>Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.</p></sec></notes><ref-list id="Bib1"><title>References</title><ref id="CR1"><label>1</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Jr</surname><given-names>HHK</given-names></name></person-group><article-title>Mobile elements: Drivers of genome evolution</article-title><source>Science</source><year>2004</year><volume>303</volume><fpage>1626</fpage><lpage>32</lpage><pub-id pub-id-type="doi">10.1126/science.1089670</pub-id><pub-id pub-id-type="pmid">15016989</pub-id></element-citation></ref><ref id="CR2"><label>2</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Cordaux</surname><given-names>R</given-names></name><name><surname>Batzer</surname><given-names>MA</given-names></name></person-group><article-title>The impact of retrotransposons on human genome evolution</article-title><source>Nat Rev Genet</source><year>2009</year><volume>10</volume><fpage>691</fpage><lpage>703</lpage><pub-id pub-id-type="doi">10.1038/nrg2640</pub-id><pub-id pub-id-type="pmid">19763152</pub-id></element-citation></ref><ref id="CR3"><label>3</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Mills</surname><given-names>RE</given-names></name><name><surname>Bennett</surname><given-names>EA</given-names></name><name><surname>Iskow</surname><given-names>RC</given-names></name><name><surname>Devine</surname><given-names>SE</given-names></name></person-group><article-title>Which transposable elements are active in the human genome?</article-title><source>Trends Genet</source><year>2007</year><volume>23</volume><issue>4</issue><fpage>183</fpage><lpage>91</lpage><pub-id pub-id-type="doi">10.1016/j.tig.2007.02.006</pub-id><pub-id pub-id-type="pmid">17331616</pub-id></element-citation></ref><ref id="CR4"><label>4</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Jurka</surname><given-names>J</given-names></name><name><surname>Kapitonov</surname><given-names>VV</given-names></name><name><surname>Pavlicek</surname><given-names>A</given-names></name><name><surname>Klonowski</surname><given-names>P</given-names></name><name><surname>Kohany</surname><given-names>O</given-names></name><name><surname>Walichiewicz</surname><given-names>J</given-names></name></person-group><article-title>Repbase Update, a database of eukaryotic repetitive elements</article-title><source>Cytogenet Genome Res</source><year>2005</year><volume>110</volume><issue>1-4</issue><fpage>462</fpage><lpage>7</lpage><pub-id pub-id-type="doi">10.1159/000084979</pub-id><pub-id pub-id-type="pmid">16093699</pub-id></element-citation></ref><ref id="CR5"><label>5</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Wheeler</surname><given-names>TJ</given-names></name><name><surname>Clements</surname><given-names>J</given-names></name><name><surname>Eddy</surname><given-names>SR</given-names></name><name><surname>Hubley</surname><given-names>R</given-names></name><name><surname>Jones</surname><given-names>TA</given-names></name><name><surname>Jurka</surname><given-names>J</given-names></name><name><surname>Smit</surname><given-names>AF</given-names></name><name><surname>Finn</surname><given-names>RD</given-names></name></person-group><article-title>Dfam: a database of repetitive dna based on profile hidden markov models</article-title><source>Nucleic Acids Res</source><year>2013</year><volume>41</volume><issue>D1</issue><fpage>70</fpage><lpage>82</lpage><pub-id pub-id-type="doi">10.1093/nar/gks1265</pub-id></element-citation></ref><ref id="CR6"><label>6</label><mixed-citation publication-type="other">Smit A, Hubley R, Green P. Repeatmasker open-4.0. 2013–2015. Institute for Systems Biology. 2015. <ext-link ext-link-type="uri" xlink:href="http://www.repeatmasker.org/faq.html">http://www.repeatmasker.org/faq.html</ext-link>.</mixed-citation></ref><ref id="CR7"><label>7</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Price</surname><given-names>AL</given-names></name><name><surname>Jones</surname><given-names>NC</given-names></name><name><surname>Pevzner</surname><given-names>PA</given-names></name></person-group><article-title>De novo identification of repeat families in large genomes</article-title><source>Bioinformatics</source><year>2005</year><volume>21</volume><issue>suppl 1</issue><fpage>351</fpage><lpage>8</lpage><pub-id pub-id-type="doi">10.1093/bioinformatics/bti1018</pub-id></element-citation></ref><ref id="CR8"><label>8</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Edgar</surname><given-names>RC</given-names></name><name><surname>Myers</surname><given-names>EW</given-names></name></person-group><article-title>Piler: identification and classification of genomic repeats</article-title><source>Bioinformatics</source><year>2005</year><volume>21</volume><issue>suppl 1</issue><fpage>152</fpage><lpage>8</lpage><pub-id pub-id-type="doi">10.1093/bioinformatics/bti1003</pub-id><pub-id pub-id-type="pmid">15377504</pub-id></element-citation></ref><ref id="CR9"><label>9</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Schaeffer</surname><given-names>CE</given-names></name><name><surname>Figueroa</surname><given-names>ND</given-names></name><name><surname>Liu</surname><given-names>X</given-names></name><name><surname>Karro</surname><given-names>JE</given-names></name></person-group><article-title>phraider: Pattern-hunter based rapid ab initio detection of elementary repeats</article-title><source>Bioinformatics</source><year>2016</year><volume>32</volume><issue>12</issue><fpage>209</fpage><lpage>15</lpage><pub-id pub-id-type="doi">10.1093/bioinformatics/btw258</pub-id></element-citation></ref><ref id="CR10"><label>10</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Koch</surname><given-names>P</given-names></name><name><surname>Platzer</surname><given-names>M</given-names></name><name><surname>Downie</surname><given-names>BR</given-names></name></person-group><article-title>RepARK - de novo creation of repeat libraries from whole-genome ngs reads</article-title><source>Nucleic Acids Res</source><year>2014</year><volume>42</volume><fpage>80</fpage><pub-id pub-id-type="doi">10.1093/nar/gku210</pub-id></element-citation></ref><ref id="CR11"><label>11</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Ye</surname><given-names>N</given-names></name><name><surname>Zhang</surname><given-names>X</given-names></name><name><surname>Miao</surname><given-names>M</given-names></name><name><surname>Fan</surname><given-names>X</given-names></name><name><surname>Zheng</surname><given-names>Y</given-names></name><name><surname>Xu</surname><given-names>D</given-names></name><name><surname>Wang</surname><given-names>J</given-names></name><name><surname>Zhou</surname><given-names>L</given-names></name><name><surname>Wang</surname><given-names>D</given-names></name><name><surname>Gao</surname><given-names>Y</given-names></name><etal></etal></person-group><article-title>Saccharina genomes provide novel insight into kelp biology</article-title><source>Nat Commun</source><year>2015</year><volume>6</volume><fpage>6986</fpage><pub-id pub-id-type="doi">10.1038/ncomms7986</pub-id><pub-id pub-id-type="pmid">25908475</pub-id></element-citation></ref><ref id="CR12"><label>12</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Chu</surname><given-names>C</given-names></name><name><surname>Nielsen</surname><given-names>R</given-names></name><name><surname>Wu</surname><given-names>Y</given-names></name></person-group><article-title>Repdenovo: Inferring de novo repeat motifs from short sequence reads</article-title><source>PloS ONE</source><year>2016</year><volume>11</volume><issue>3</issue><fpage>0150719</fpage></element-citation></ref><ref id="CR13"><label>13</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Zerbino</surname><given-names>DR</given-names></name><name><surname>Birney</surname><given-names>E</given-names></name></person-group><article-title>Velvet: algorithms for de novo short read assembly using de bruijn graphs</article-title><source>Genome Res</source><year>2008</year><volume>18</volume><issue>5</issue><fpage>821</fpage><lpage>9</lpage><pub-id pub-id-type="doi">10.1101/gr.074492.107</pub-id><pub-id pub-id-type="pmid">18349386</pub-id></element-citation></ref><ref id="CR14"><label>14</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Robinson</surname><given-names>JT</given-names></name><name><surname>Thorvaldsdóttir</surname><given-names>H</given-names></name><name><surname>Winckler</surname><given-names>W</given-names></name><name><surname>Guttman</surname><given-names>M</given-names></name><name><surname>ES Lander</surname><given-names>ea</given-names></name></person-group><article-title>Integrative genomics viewer</article-title><source>Nat Biotechnol</source><year>2011</year><volume>29</volume><fpage>24</fpage><lpage>6</lpage><pub-id pub-id-type="doi">10.1038/nbt.1754</pub-id><pub-id pub-id-type="pmid">21221095</pub-id></element-citation></ref><ref id="CR15"><label>15</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Li</surname><given-names>H</given-names></name><name><surname>Durbin</surname><given-names>R</given-names></name></person-group><article-title>Fast and accurate short read alignment with Burrows–Wheeler transform</article-title><source>Bioinformatics</source><year>2009</year><volume>25</volume><issue>14</issue><fpage>1754</fpage><lpage>60</lpage><pub-id pub-id-type="doi">10.1093/bioinformatics/btp324</pub-id><pub-id pub-id-type="pmid">19451168</pub-id></element-citation></ref><ref id="CR16"><label>16</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Consortium</surname><given-names>GP</given-names></name><etal></etal></person-group><article-title>An integrated map of genetic variation from 1,092 human genomes</article-title><source>Nature</source><year>2012</year><volume>491</volume><issue>7422</issue><fpage>56</fpage><lpage>65</lpage><pub-id pub-id-type="doi">10.1038/nature11632</pub-id><pub-id pub-id-type="pmid">23128226</pub-id></element-citation></ref><ref id="CR17"><label>17</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Chin</surname><given-names>C-S</given-names></name><name><surname>Peluso</surname><given-names>P</given-names></name><name><surname>Sedlazeck</surname><given-names>FJ</given-names></name><name><surname>Nattestad</surname><given-names>M</given-names></name><name><surname>Concepcion</surname><given-names>GT</given-names></name><name><surname>Clum</surname><given-names>A</given-names></name><name><surname>Dunn</surname><given-names>C</given-names></name><name><surname>O’Malley</surname><given-names>R</given-names></name><name><surname>Figueroa-Balderas</surname><given-names>R</given-names></name><name><surname>Morales-Cruz</surname><given-names>A</given-names></name><etal></etal></person-group><article-title>Phased diploid genome assembly with single-molecule real-time sequencing</article-title><source>Nat Methods</source><year>2016</year><volume>13</volume><issue>12</issue><fpage>1050</fpage><lpage>4</lpage><pub-id pub-id-type="doi">10.1038/nmeth.4035</pub-id><pub-id pub-id-type="pmid">27749838</pub-id></element-citation></ref><ref id="CR18"><label>18</label><element-citation publication-type="journal"><person-group person-group-type="author"><name><surname>Rosenbloom</surname><given-names>KR</given-names></name><name><surname>Armstrong</surname><given-names>J</given-names></name><name><surname>Barber</surname><given-names>GP</given-names></name><name><surname>Casper</surname><given-names>J</given-names></name><name><surname>Clawson</surname><given-names>H</given-names></name><name><surname>Diekhans</surname><given-names>M</given-names></name><name><surname>Dreszer</surname><given-names>TR</given-names></name><name><surname>Fujita</surname><given-names>PA</given-names></name><name><surname>Guruvadoo</surname><given-names>L</given-names></name><name><surname>Haeussler</surname><given-names>M</given-names></name><etal></etal></person-group><article-title>The ucsc genome browser database: 2015 update</article-title><source>Nucleic Acids Res</source><year>2015</year><volume>43</volume><issue>D1</issue><fpage>670</fpage><lpage>81</lpage><pub-id pub-id-type="doi">10.1093/nar/gku1177</pub-id></element-citation></ref><ref id="CR19"><label>19</label><mixed-citation publication-type="other">Korlach J, Gedman G, King S, Chin J, Howard J, Cantin L, Jarvis ED. De novo pacbio long-read and phased avian genome assemblies correct and add to genes important in neuroscience research. bioRxiv. 2017:103911. Cold Spring Harbor Laboratory.</mixed-citation></ref><ref id="CR20"><label>20</label><mixed-citation publication-type="other">Bioinformatics Research and Applications : 13th International Symposium, ISBRA 2017, Honolulu, HI, USA, May 29-June 2, 2017, Proceedings. 2017.</mixed-citation></ref></ref-list></back></pmc></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Sante/explor/MersV1/Data/Pmc/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000298 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd -nk 000298 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Sante
|area= MersV1
|flux= Pmc
|étape= Corpus
|type= RBID
|clé= PMC:6101065
|texte= An improved approach for reconstructing consensus repeats from short sequence reads
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Pmc/Corpus/RBID.i -Sk "pubmed:30367582" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Pmc/Corpus/biblio.hfd \
| NlmPubMed2Wicri -a MersV1
| This area was generated with Dilib version V0.6.33. |  |