Eintrag weiter verarbeiten
A practical method for exact computation of subtree prune and regraft distance
Gespeichert in:
| Zeitschriftentitel: | Bioinformatics |
|---|---|
| Personen und Körperschaften: | |
| In: | Bioinformatics, 25, 2009, 2, S. 190-196 |
| Format: | E-Article |
| Sprache: | Englisch |
| veröffentlicht: |
Oxford University Press (OUP)
|
| Schlagwörter: |
| author_facet |
Wu, Yufeng Wu, Yufeng |
|---|---|
| author |
Wu, Yufeng |
| spellingShingle |
Wu, Yufeng Bioinformatics A practical method for exact computation of subtree prune and regraft distance Computational Mathematics Computational Theory and Mathematics Computer Science Applications Molecular Biology Biochemistry Statistics and Probability |
| author_sort |
wu, yufeng |
| spelling |
Wu, Yufeng 1367-4811 1367-4803 Oxford University Press (OUP) Computational Mathematics Computational Theory and Mathematics Computer Science Applications Molecular Biology Biochemistry Statistics and Probability http://dx.doi.org/10.1093/bioinformatics/btn606 <jats:title>Abstract</jats:title> <jats:p>Motivation: Subtree prune and regraft (SPR) is one kind of tree rearrangements that has seen applications in solving several computational biology problems. The minimum number of rooted SPR (rSPR) operations needed to transform one rooted binary tree to another is called the rSPR distance between the two trees. Computing the rSPR distance has been actively studied in recent years. Currently, there is a lack of practical software tools for computing the rSPR distance for relatively large trees with large rSPR distance.</jats:p> <jats:p>Results: In this article, we present a simple and practical method that computes the exact rSPR distance with integer linear programming. By applying this new method on several simulated and real biological datasets, we show that our new method outperforms existing software tools in term of accuracy and ef.ciency. Our experimental results indicate that our method can compute the exact rSPR distance for many large trees with large rSPR distance.</jats:p> <jats:p>Availability: A software tool, SPRDist, is available for download from the web page: http://www.engr.uconn.edu/~ywu.</jats:p> <jats:p>Contact: ywu@engr.uconn.edu</jats:p> A practical method for exact computation of subtree prune and regraft distance Bioinformatics |
| doi_str_mv |
10.1093/bioinformatics/btn606 |
| facet_avail |
Online Free |
| finc_class_facet |
Mathematik Informatik Biologie Chemie und Pharmazie |
| format |
ElectronicArticle |
| fullrecord |
blob:ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTA5My9iaW9pbmZvcm1hdGljcy9idG42MDY |
| id |
ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTA5My9iaW9pbmZvcm1hdGljcy9idG42MDY |
| institution |
DE-Ch1 DE-L229 DE-D275 DE-Bn3 DE-Brt1 DE-Zwi2 DE-D161 DE-Gla1 DE-Zi4 DE-15 DE-Rs1 DE-Pl11 DE-105 DE-14 |
| imprint |
Oxford University Press (OUP), 2009 |
| imprint_str_mv |
Oxford University Press (OUP), 2009 |
| issn |
1367-4811 1367-4803 |
| issn_str_mv |
1367-4811 1367-4803 |
| language |
English |
| mega_collection |
Oxford University Press (OUP) (CrossRef) |
| match_str |
wu2009apracticalmethodforexactcomputationofsubtreepruneandregraftdistance |
| publishDateSort |
2009 |
| publisher |
Oxford University Press (OUP) |
| recordtype |
ai |
| record_format |
ai |
| series |
Bioinformatics |
| source_id |
49 |
| title |
A practical method for exact computation of subtree prune and regraft distance |
| title_unstemmed |
A practical method for exact computation of subtree prune and regraft distance |
| title_full |
A practical method for exact computation of subtree prune and regraft distance |
| title_fullStr |
A practical method for exact computation of subtree prune and regraft distance |
| title_full_unstemmed |
A practical method for exact computation of subtree prune and regraft distance |
| title_short |
A practical method for exact computation of subtree prune and regraft distance |
| title_sort |
a practical method for exact computation of subtree prune and regraft distance |
| topic |
Computational Mathematics Computational Theory and Mathematics Computer Science Applications Molecular Biology Biochemistry Statistics and Probability |
| url |
http://dx.doi.org/10.1093/bioinformatics/btn606 |
| publishDate |
2009 |
| physical |
190-196 |
| description |
<jats:title>Abstract</jats:title>
<jats:p>Motivation: Subtree prune and regraft (SPR) is one kind of tree rearrangements that has seen applications in solving several computational biology problems. The minimum number of rooted SPR (rSPR) operations needed to transform one rooted binary tree to another is called the rSPR distance between the two trees. Computing the rSPR distance has been actively studied in recent years. Currently, there is a lack of practical software tools for computing the rSPR distance for relatively large trees with large rSPR distance.</jats:p>
<jats:p>Results: In this article, we present a simple and practical method that computes the exact rSPR distance with integer linear programming. By applying this new method on several simulated and real biological datasets, we show that our new method outperforms existing software tools in term of accuracy and ef.ciency. Our experimental results indicate that our method can compute the exact rSPR distance for many large trees with large rSPR distance.</jats:p>
<jats:p>Availability: A software tool, SPRDist, is available for download from the web page: http://www.engr.uconn.edu/~ywu.</jats:p>
<jats:p>Contact: ywu@engr.uconn.edu</jats:p> |
| container_issue |
2 |
| container_start_page |
190 |
| container_title |
Bioinformatics |
| container_volume |
25 |
| format_de105 |
Article, E-Article |
| format_de14 |
Article, E-Article |
| format_de15 |
Article, E-Article |
| format_de520 |
Article, E-Article |
| format_de540 |
Article, E-Article |
| format_dech1 |
Article, E-Article |
| format_ded117 |
Article, E-Article |
| format_degla1 |
E-Article |
| format_del152 |
Buch |
| format_del189 |
Article, E-Article |
| format_dezi4 |
Article |
| format_dezwi2 |
Article, E-Article |
| format_finc |
Article, E-Article |
| format_nrw |
Article, E-Article |
| _version_ |
1792344877456949255 |
| geogr_code |
not assigned |
| last_indexed |
2024-03-01T17:14:05.871Z |
| geogr_code_person |
not assigned |
| openURL |
url_ver=Z39.88-2004&ctx_ver=Z39.88-2004&ctx_enc=info%3Aofi%2Fenc%3AUTF-8&rfr_id=info%3Asid%2Fvufind.svn.sourceforge.net%3Agenerator&rft.title=A+practical+method+for+exact+computation+of+subtree+prune+and+regraft+distance&rft.date=2009-01-15&genre=article&issn=1367-4803&volume=25&issue=2&spage=190&epage=196&pages=190-196&jtitle=Bioinformatics&atitle=A+practical+method+for+exact+computation+of+subtree+prune+and+regraft+distance&aulast=Wu&aufirst=Yufeng&rft_id=info%3Adoi%2F10.1093%2Fbioinformatics%2Fbtn606&rft.language%5B0%5D=eng |
| SOLR | |
| _version_ | 1792344877456949255 |
| author | Wu, Yufeng |
| author_facet | Wu, Yufeng, Wu, Yufeng |
| author_sort | wu, yufeng |
| container_issue | 2 |
| container_start_page | 190 |
| container_title | Bioinformatics |
| container_volume | 25 |
| description | <jats:title>Abstract</jats:title> <jats:p>Motivation: Subtree prune and regraft (SPR) is one kind of tree rearrangements that has seen applications in solving several computational biology problems. The minimum number of rooted SPR (rSPR) operations needed to transform one rooted binary tree to another is called the rSPR distance between the two trees. Computing the rSPR distance has been actively studied in recent years. Currently, there is a lack of practical software tools for computing the rSPR distance for relatively large trees with large rSPR distance.</jats:p> <jats:p>Results: In this article, we present a simple and practical method that computes the exact rSPR distance with integer linear programming. By applying this new method on several simulated and real biological datasets, we show that our new method outperforms existing software tools in term of accuracy and ef.ciency. Our experimental results indicate that our method can compute the exact rSPR distance for many large trees with large rSPR distance.</jats:p> <jats:p>Availability: A software tool, SPRDist, is available for download from the web page: http://www.engr.uconn.edu/~ywu.</jats:p> <jats:p>Contact: ywu@engr.uconn.edu</jats:p> |
| doi_str_mv | 10.1093/bioinformatics/btn606 |
| facet_avail | Online, Free |
| finc_class_facet | Mathematik, Informatik, Biologie, Chemie und Pharmazie |
| format | ElectronicArticle |
| format_de105 | Article, E-Article |
| format_de14 | Article, E-Article |
| format_de15 | Article, E-Article |
| format_de520 | Article, E-Article |
| format_de540 | Article, E-Article |
| format_dech1 | Article, E-Article |
| format_ded117 | Article, E-Article |
| format_degla1 | E-Article |
| format_del152 | Buch |
| format_del189 | Article, E-Article |
| format_dezi4 | Article |
| format_dezwi2 | Article, E-Article |
| format_finc | Article, E-Article |
| format_nrw | Article, E-Article |
| geogr_code | not assigned |
| geogr_code_person | not assigned |
| id | ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTA5My9iaW9pbmZvcm1hdGljcy9idG42MDY |
| imprint | Oxford University Press (OUP), 2009 |
| imprint_str_mv | Oxford University Press (OUP), 2009 |
| institution | DE-Ch1, DE-L229, DE-D275, DE-Bn3, DE-Brt1, DE-Zwi2, DE-D161, DE-Gla1, DE-Zi4, DE-15, DE-Rs1, DE-Pl11, DE-105, DE-14 |
| issn | 1367-4811, 1367-4803 |
| issn_str_mv | 1367-4811, 1367-4803 |
| language | English |
| last_indexed | 2024-03-01T17:14:05.871Z |
| match_str | wu2009apracticalmethodforexactcomputationofsubtreepruneandregraftdistance |
| mega_collection | Oxford University Press (OUP) (CrossRef) |
| physical | 190-196 |
| publishDate | 2009 |
| publishDateSort | 2009 |
| publisher | Oxford University Press (OUP) |
| record_format | ai |
| recordtype | ai |
| series | Bioinformatics |
| source_id | 49 |
| spelling | Wu, Yufeng 1367-4811 1367-4803 Oxford University Press (OUP) Computational Mathematics Computational Theory and Mathematics Computer Science Applications Molecular Biology Biochemistry Statistics and Probability http://dx.doi.org/10.1093/bioinformatics/btn606 <jats:title>Abstract</jats:title> <jats:p>Motivation: Subtree prune and regraft (SPR) is one kind of tree rearrangements that has seen applications in solving several computational biology problems. The minimum number of rooted SPR (rSPR) operations needed to transform one rooted binary tree to another is called the rSPR distance between the two trees. Computing the rSPR distance has been actively studied in recent years. Currently, there is a lack of practical software tools for computing the rSPR distance for relatively large trees with large rSPR distance.</jats:p> <jats:p>Results: In this article, we present a simple and practical method that computes the exact rSPR distance with integer linear programming. By applying this new method on several simulated and real biological datasets, we show that our new method outperforms existing software tools in term of accuracy and ef.ciency. Our experimental results indicate that our method can compute the exact rSPR distance for many large trees with large rSPR distance.</jats:p> <jats:p>Availability: A software tool, SPRDist, is available for download from the web page: http://www.engr.uconn.edu/~ywu.</jats:p> <jats:p>Contact: ywu@engr.uconn.edu</jats:p> A practical method for exact computation of subtree prune and regraft distance Bioinformatics |
| spellingShingle | Wu, Yufeng, Bioinformatics, A practical method for exact computation of subtree prune and regraft distance, Computational Mathematics, Computational Theory and Mathematics, Computer Science Applications, Molecular Biology, Biochemistry, Statistics and Probability |
| title | A practical method for exact computation of subtree prune and regraft distance |
| title_full | A practical method for exact computation of subtree prune and regraft distance |
| title_fullStr | A practical method for exact computation of subtree prune and regraft distance |
| title_full_unstemmed | A practical method for exact computation of subtree prune and regraft distance |
| title_short | A practical method for exact computation of subtree prune and regraft distance |
| title_sort | a practical method for exact computation of subtree prune and regraft distance |
| title_unstemmed | A practical method for exact computation of subtree prune and regraft distance |
| topic | Computational Mathematics, Computational Theory and Mathematics, Computer Science Applications, Molecular Biology, Biochemistry, Statistics and Probability |
| url | http://dx.doi.org/10.1093/bioinformatics/btn606 |