Exploring the space of gene/species reconciliations with transfers.
Identifieur interne : 002094 ( Ncbi/Merge ); précédent : 002093; suivant : 002095Exploring the space of gene/species reconciliations with transfers.
Auteurs : Yao-Ban Chan [Australie] ; Vincent Ranwez [France] ; Céline Scornavacca [France]Source :
- Journal of mathematical biology [ 1432-1416 ] ; 2015.
Descripteurs français
- KwdFr :
- MESH :
English descriptors
- KwdEn :
- MESH :
Abstract
Reconciliations between gene and species trees have important applications in the study of genome evolution (e.g. sequence orthology prediction or quantification of transfer events). While numerous methods have been proposed to infer them, little has been done to study the underlying reconciliation space. In this paper, we characterise the reconciliation space for two evolutionary models: the [Formula: see text] (duplication, loss and transfer) model and a variant of it-the no-[Formula: see text] model-which does not allow [Formula: see text] events (a transfer immediately followed by a loss). We provide formulae to compute the size of the corresponding spaces and define a set of transformation operators sufficient to explore the entire reconciliation space. We also define a distance between two reconciliations as the minimal number of operations needed to transform one into the other and prove that this distance is easily computable in the no-[Formula: see text] model. Computing this distance in the [Formula: see text] model is more difficult and it is an open question whether it is NP-hard or not. This work constitutes an important step toward reconciliation space characterisation and reconciliation comparison, needed to better assess the performance of reconciliation inference methods through simulations.
DOI: 10.1007/s00285-014-0851-2
PubMed: 25502987
Links toward previous steps (curation, corpus...)
- to stream PubMed, to step Corpus: 002807
- to stream PubMed, to step Curation: 002738
- to stream PubMed, to step Checkpoint: 002738
Links to Exploration step
pubmed:25502987Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en">Exploring the space of gene/species reconciliations with transfers.</title><author><name sortKey="Chan, Yao Ban" sort="Chan, Yao Ban" uniqKey="Chan Y" first="Yao-Ban" last="Chan">Yao-Ban Chan</name><affiliation wicri:level="1"><nlm:affiliation>School of Mathematics and Physics, The University of Queensland, St. Lucia, QLD, 4072, Australia. yaoban.chan@uq.edu.au.</nlm:affiliation><country xml:lang="fr">Australie</country><wicri:regionArea>School of Mathematics and Physics, The University of Queensland, St. Lucia, QLD, 4072</wicri:regionArea><wicri:noRegion>4072</wicri:noRegion></affiliation></author><author><name sortKey="Ranwez, Vincent" sort="Ranwez, Vincent" uniqKey="Ranwez V" first="Vincent" last="Ranwez">Vincent Ranwez</name><affiliation wicri:level="1"><nlm:affiliation>Montpellier SupAgro (UMR AGAP), 2 place Pierre Viala, Montpellier Cedex 02, 34060, France. ranwez@supagro.inra.fr.</nlm:affiliation><country xml:lang="fr">France</country><wicri:regionArea>Montpellier SupAgro (UMR AGAP), 2 place Pierre Viala, Montpellier Cedex 02, 34060</wicri:regionArea><wicri:noRegion>34060</wicri:noRegion><wicri:noRegion>34060</wicri:noRegion></affiliation></author><author><name sortKey="Scornavacca, Celine" sort="Scornavacca, Celine" uniqKey="Scornavacca C" first="Céline" last="Scornavacca">Céline Scornavacca</name><affiliation wicri:level="4"><nlm:affiliation>Institut des Sciences de l'Evolution (ISEM, UMR 5554 CNRS), Université Montpellier II, Place E. Bataillon-CC 064, Montpellier Cedex 5, 34095, France. celine.scornavacca@univ-montp2.fr.</nlm:affiliation><country xml:lang="fr">France</country><wicri:regionArea>Institut des Sciences de l'Evolution (ISEM, UMR 5554 CNRS), Université Montpellier II, Place E. Bataillon-CC 064, Montpellier Cedex 5, 34095</wicri:regionArea><wicri:noRegion>34095</wicri:noRegion><orgName type="university">Université Montpellier 2</orgName><placeName><settlement type="city">Montpellier</settlement><region type="region" nuts="2">Occitanie (région administrative)</region><region type="old region" nuts="2">Languedoc-Roussillon</region></placeName></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">PubMed</idno><date when="2015">2015</date><idno type="RBID">pubmed:25502987</idno><idno type="pmid">25502987</idno><idno type="doi">10.1007/s00285-014-0851-2</idno><idno type="wicri:Area/PubMed/Corpus">002807</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Corpus" wicri:corpus="PubMed">002807</idno><idno type="wicri:Area/PubMed/Curation">002738</idno><idno type="wicri:explorRef" wicri:stream="PubMed" wicri:step="Curation">002738</idno><idno type="wicri:Area/PubMed/Checkpoint">002738</idno><idno type="wicri:explorRef" wicri:stream="Checkpoint" wicri:step="PubMed">002738</idno><idno type="wicri:Area/Ncbi/Merge">002094</idno></publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en">Exploring the space of gene/species reconciliations with transfers.</title><author><name sortKey="Chan, Yao Ban" sort="Chan, Yao Ban" uniqKey="Chan Y" first="Yao-Ban" last="Chan">Yao-Ban Chan</name><affiliation wicri:level="1"><nlm:affiliation>School of Mathematics and Physics, The University of Queensland, St. Lucia, QLD, 4072, Australia. yaoban.chan@uq.edu.au.</nlm:affiliation><country xml:lang="fr">Australie</country><wicri:regionArea>School of Mathematics and Physics, The University of Queensland, St. Lucia, QLD, 4072</wicri:regionArea><wicri:noRegion>4072</wicri:noRegion></affiliation></author><author><name sortKey="Ranwez, Vincent" sort="Ranwez, Vincent" uniqKey="Ranwez V" first="Vincent" last="Ranwez">Vincent Ranwez</name><affiliation wicri:level="1"><nlm:affiliation>Montpellier SupAgro (UMR AGAP), 2 place Pierre Viala, Montpellier Cedex 02, 34060, France. ranwez@supagro.inra.fr.</nlm:affiliation><country xml:lang="fr">France</country><wicri:regionArea>Montpellier SupAgro (UMR AGAP), 2 place Pierre Viala, Montpellier Cedex 02, 34060</wicri:regionArea><wicri:noRegion>34060</wicri:noRegion><wicri:noRegion>34060</wicri:noRegion></affiliation></author><author><name sortKey="Scornavacca, Celine" sort="Scornavacca, Celine" uniqKey="Scornavacca C" first="Céline" last="Scornavacca">Céline Scornavacca</name><affiliation wicri:level="4"><nlm:affiliation>Institut des Sciences de l'Evolution (ISEM, UMR 5554 CNRS), Université Montpellier II, Place E. Bataillon-CC 064, Montpellier Cedex 5, 34095, France. celine.scornavacca@univ-montp2.fr.</nlm:affiliation><country xml:lang="fr">France</country><wicri:regionArea>Institut des Sciences de l'Evolution (ISEM, UMR 5554 CNRS), Université Montpellier II, Place E. Bataillon-CC 064, Montpellier Cedex 5, 34095</wicri:regionArea><wicri:noRegion>34095</wicri:noRegion><orgName type="university">Université Montpellier 2</orgName><placeName><settlement type="city">Montpellier</settlement><region type="region" nuts="2">Occitanie (région administrative)</region><region type="old region" nuts="2">Languedoc-Roussillon</region></placeName></affiliation></author></analytic><series><title level="j">Journal of mathematical biology</title><idno type="eISSN">1432-1416</idno><imprint><date when="2015" type="published">2015</date></imprint></series></biblStruct></sourceDesc></fileDesc><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithms</term><term>Computer Simulation</term><term>Evolution, Molecular</term><term>Gene Deletion</term><term>Gene Duplication</term><term>Gene Transfer, Horizontal</term><term>Genetic Speciation</term><term>Mathematical Concepts</term><term>Models, Genetic</term><term>Multigene Family</term><term>Phylogeny</term><term>Species Specificity</term></keywords><keywords scheme="KwdFr" xml:lang="fr"><term>Algorithmes</term><term>Concepts mathématiques</term><term>Duplication de gène</term><term>Délétion de gène</term><term>Famille multigénique</term><term>Modèles génétiques</term><term>Phylogénie</term><term>Simulation numérique</term><term>Spéciation génétique</term><term>Spécificité d'espèce</term><term>Transfert horizontal de gène</term><term>Évolution moléculaire</term></keywords><keywords scheme="MESH" xml:lang="en"><term>Algorithms</term><term>Computer Simulation</term><term>Evolution, Molecular</term><term>Gene Deletion</term><term>Gene Duplication</term><term>Gene Transfer, Horizontal</term><term>Genetic Speciation</term><term>Mathematical Concepts</term><term>Models, Genetic</term><term>Multigene Family</term><term>Phylogeny</term><term>Species Specificity</term></keywords><keywords scheme="MESH" xml:lang="fr"><term>Algorithmes</term><term>Concepts mathématiques</term><term>Duplication de gène</term><term>Délétion de gène</term><term>Famille multigénique</term><term>Modèles génétiques</term><term>Phylogénie</term><term>Simulation numérique</term><term>Spéciation génétique</term><term>Spécificité d'espèce</term><term>Transfert horizontal de gène</term><term>Évolution moléculaire</term></keywords></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Reconciliations between gene and species trees have important applications in the study of genome evolution (e.g. sequence orthology prediction or quantification of transfer events). While numerous methods have been proposed to infer them, little has been done to study the underlying reconciliation space. In this paper, we characterise the reconciliation space for two evolutionary models: the [Formula: see text] (duplication, loss and transfer) model and a variant of it-the no-[Formula: see text] model-which does not allow [Formula: see text] events (a transfer immediately followed by a loss). We provide formulae to compute the size of the corresponding spaces and define a set of transformation operators sufficient to explore the entire reconciliation space. We also define a distance between two reconciliations as the minimal number of operations needed to transform one into the other and prove that this distance is easily computable in the no-[Formula: see text] model. Computing this distance in the [Formula: see text] model is more difficult and it is an open question whether it is NP-hard or not. This work constitutes an important step toward reconciliation space characterisation and reconciliation comparison, needed to better assess the performance of reconciliation inference methods through simulations.</div></front></TEI><pubmed><MedlineCitation Status="MEDLINE" Owner="NLM"><PMID Version="1">25502987</PMID><DateCreated><Year>2015</Year><Month>10</Month><Day>09</Day></DateCreated><DateCompleted><Year>2016</Year><Month>07</Month><Day>25</Day></DateCompleted><DateRevised><Year>2017</Year><Month>09</Month><Day>26</Day></DateRevised><Article PubModel="Print-Electronic"><Journal><ISSN IssnType="Electronic">1432-1416</ISSN><JournalIssue CitedMedium="Internet"><Volume>71</Volume><Issue>5</Issue><PubDate><Year>2015</Year><Month>Nov</Month></PubDate></JournalIssue><Title>Journal of mathematical biology</Title><ISOAbbreviation>J Math Biol</ISOAbbreviation></Journal><ArticleTitle>Exploring the space of gene/species reconciliations with transfers.</ArticleTitle><Pagination><MedlinePgn>1179-209</MedlinePgn></Pagination><ELocationID EIdType="doi" ValidYN="Y">10.1007/s00285-014-0851-2</ELocationID><Abstract><AbstractText>Reconciliations between gene and species trees have important applications in the study of genome evolution (e.g. sequence orthology prediction or quantification of transfer events). While numerous methods have been proposed to infer them, little has been done to study the underlying reconciliation space. In this paper, we characterise the reconciliation space for two evolutionary models: the [Formula: see text] (duplication, loss and transfer) model and a variant of it-the no-[Formula: see text] model-which does not allow [Formula: see text] events (a transfer immediately followed by a loss). We provide formulae to compute the size of the corresponding spaces and define a set of transformation operators sufficient to explore the entire reconciliation space. We also define a distance between two reconciliations as the minimal number of operations needed to transform one into the other and prove that this distance is easily computable in the no-[Formula: see text] model. Computing this distance in the [Formula: see text] model is more difficult and it is an open question whether it is NP-hard or not. This work constitutes an important step toward reconciliation space characterisation and reconciliation comparison, needed to better assess the performance of reconciliation inference methods through simulations.</AbstractText></Abstract><AuthorList CompleteYN="Y"><Author ValidYN="Y"><LastName>Chan</LastName><ForeName>Yao-Ban</ForeName><Initials>YB</Initials><AffiliationInfo><Affiliation>School of Mathematics and Physics, The University of Queensland, St. Lucia, QLD, 4072, Australia. yaoban.chan@uq.edu.au.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Ranwez</LastName><ForeName>Vincent</ForeName><Initials>V</Initials><AffiliationInfo><Affiliation>Montpellier SupAgro (UMR AGAP), 2 place Pierre Viala, Montpellier Cedex 02, 34060, France. ranwez@supagro.inra.fr.</Affiliation></AffiliationInfo></Author><Author ValidYN="Y"><LastName>Scornavacca</LastName><ForeName>Céline</ForeName><Initials>C</Initials><AffiliationInfo><Affiliation>Institut des Sciences de l'Evolution (ISEM, UMR 5554 CNRS), Université Montpellier II, Place E. Bataillon-CC 064, Montpellier Cedex 5, 34095, France. celine.scornavacca@univ-montp2.fr.</Affiliation></AffiliationInfo></Author></AuthorList><Language>eng</Language><PublicationTypeList><PublicationType UI="D016428">Journal Article</PublicationType><PublicationType UI="D013485">Research Support, Non-U.S. Gov't</PublicationType></PublicationTypeList><ArticleDate DateType="Electronic"><Year>2014</Year><Month>12</Month><Day>14</Day></ArticleDate></Article><MedlineJournalInfo><Country>Germany</Country><MedlineTA>J Math Biol</MedlineTA><NlmUniqueID>7502105</NlmUniqueID><ISSNLinking>0303-6812</ISSNLinking></MedlineJournalInfo><CitationSubset>IM</CitationSubset><CommentsCorrectionsList><CommentsCorrections RefType="Cites"><RefSource>PLoS One. 2013 Oct 04;8(10):e73667</RefSource><PMID Version="1">24124449</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>Syst Biol. 2013 Nov;62(6):901-12</RefSource><PMID Version="1">23925510</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>Mol Biol Evol. 2004 Jun;21(6):1095-109</RefSource><PMID Version="1">15014145</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>J Bioinform Comput Biol. 2013 Apr;11(2):1250025</RefSource><PMID Version="1">23600816</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>IEEE/ACM Trans Comput Biol Bioinform. 2011 Mar-Apr;8(2):517-35</RefSource><PMID Version="1">21233529</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>Bioinformatics. 2002 Jan;18(1):92-9</RefSource><PMID Version="1">11836216</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>J Comput Biol. 2009 Oct;16(10):1399-418</RefSource><PMID Version="1">19754270</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>BMC Bioinformatics. 2007 Mar 08;8:83</RefSource><PMID Version="1">17346331</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>Proc Natl Acad Sci U S A. 2012 Mar 27;109(13):4962-7</RefSource><PMID Version="1">22416123</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>Mol Biol Evol. 2011 Jan;28(1):273-90</RefSource><PMID Version="1">20660489</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>Genome Res. 2013 Feb;23(2):323-30</RefSource><PMID Version="1">23132911</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>BMC Bioinformatics. 2010 Jun 15;11:324</RefSource><PMID Version="1">20550700</PMID></CommentsCorrections><CommentsCorrections RefType="Cites"><RefSource>Proc Natl Acad Sci U S A. 2009 Apr 7;106(14):5714-9</RefSource><PMID Version="1">19299507</PMID></CommentsCorrections></CommentsCorrectionsList><MeshHeadingList><MeshHeading><DescriptorName UI="D000465" MajorTopicYN="N">Algorithms</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D003198" MajorTopicYN="N">Computer Simulation</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D019143" MajorTopicYN="Y">Evolution, Molecular</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D017353" MajorTopicYN="N">Gene Deletion</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D020440" MajorTopicYN="N">Gene Duplication</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D022761" MajorTopicYN="N">Gene Transfer, Horizontal</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D049810" MajorTopicYN="N">Genetic Speciation</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D055641" MajorTopicYN="N">Mathematical Concepts</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D008957" MajorTopicYN="Y">Models, Genetic</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D005810" MajorTopicYN="N">Multigene Family</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D010802" MajorTopicYN="Y">Phylogeny</DescriptorName></MeshHeading><MeshHeading><DescriptorName UI="D013045" MajorTopicYN="N">Species Specificity</DescriptorName></MeshHeading></MeshHeadingList><KeywordList Owner="NOTNLM"><Keyword MajorTopicYN="N">Counting</Keyword><Keyword MajorTopicYN="N">Distance</Keyword><Keyword MajorTopicYN="N">Gene duplication</Keyword><Keyword MajorTopicYN="N">Gene transfer</Keyword><Keyword MajorTopicYN="N">Phylogenomics</Keyword><Keyword MajorTopicYN="N">Reconciliation</Keyword><Keyword MajorTopicYN="N">Sampling</Keyword></KeywordList></MedlineCitation><PubmedData><History><PubMedPubDate PubStatus="received"><Year>2013</Year><Month>05</Month><Day>21</Day></PubMedPubDate><PubMedPubDate PubStatus="revised"><Year>2014</Year><Month>07</Month><Day>11</Day></PubMedPubDate><PubMedPubDate PubStatus="entrez"><Year>2014</Year><Month>12</Month><Day>16</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="pubmed"><Year>2014</Year><Month>12</Month><Day>17</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate><PubMedPubDate PubStatus="medline"><Year>2016</Year><Month>7</Month><Day>28</Day><Hour>6</Hour><Minute>0</Minute></PubMedPubDate></History><PublicationStatus>ppublish</PublicationStatus><ArticleIdList><ArticleId IdType="pubmed">25502987</ArticleId><ArticleId IdType="doi">10.1007/s00285-014-0851-2</ArticleId><ArticleId IdType="pii">10.1007/s00285-014-0851-2</ArticleId></ArticleIdList></PubmedData></pubmed><affiliations><list><country><li>Australie</li><li>France</li></country><region><li>Languedoc-Roussillon</li><li>Occitanie (région administrative)</li></region><settlement><li>Montpellier</li></settlement><orgName><li>Université Montpellier 2</li></orgName></list><tree><country name="Australie"><noRegion><name sortKey="Chan, Yao Ban" sort="Chan, Yao Ban" uniqKey="Chan Y" first="Yao-Ban" last="Chan">Yao-Ban Chan</name></noRegion></country><country name="France"><noRegion><name sortKey="Ranwez, Vincent" sort="Ranwez, Vincent" uniqKey="Ranwez V" first="Vincent" last="Ranwez">Vincent Ranwez</name></noRegion><name sortKey="Scornavacca, Celine" sort="Scornavacca, Celine" uniqKey="Scornavacca C" first="Céline" last="Scornavacca">Céline Scornavacca</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Asie/explor/AustralieFrV1/Data/Ncbi/Merge
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002094 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd -nk 002094 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Asie
|area= AustralieFrV1
|flux= Ncbi
|étape= Merge
|type= RBID
|clé= pubmed:25502987
|texte= Exploring the space of gene/species reconciliations with transfers.
}}
Pour générer des pages wiki
HfdIndexSelect -h $EXPLOR_AREA/Data/Ncbi/Merge/RBID.i -Sk "pubmed:25502987" \
| HfdSelect -Kh $EXPLOR_AREA/Data/Ncbi/Merge/biblio.hfd \
| NlmPubMed2Wicri -a AustralieFrV1
| This area was generated with Dilib version V0.6.33. |  |