東華大學圖書館 |

Language: English

Help

回圖書館首頁

手機版館藏查詢

Back

Switch To: Labeled | MARC Mode | ISBD

High-performance algorithms for phyl...

Yan, Mi.

Linked to FindBook

Google Book

Amazon

博客來

High-performance algorithms for phylogeny reconstruction with maximum parsimony.

Record Type:	Electronic resources : Monograph/item
Title/Author:	High-performance algorithms for phylogeny reconstruction with maximum parsimony./
Author:	Yan, Mi.
Description:	96 p.
Notes:	Source: Dissertation Abstracts International, Volume: 65-04, Section: B, page: 1962.
Contained By:	Dissertation Abstracts International65-04B.
Subject:	Computer Science. -
Online resource:	http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3129663
ISBN:	0496769217

High-performance algorithms for phylogeny reconstruction with maximum parsimony.
Yan, Mi.

High-performance algorithms for phylogeny reconstruction with maximum parsimony. - 96 p.

Source: Dissertation Abstracts International, Volume: 65-04, Section: B, page: 1962.

Thesis (Ph.D.)--The University of New Mexico, 2004.

Phylogeny usually represented by an unrooted binary tree shows the evolutionary history of a set of species. Phylogenies derived from molecular data may prove crucial in answering some fundamental open questions in molecular evolution, and phylogeny reconstruction is a key research problem in computational biology. Biologists now study genomic sequences: DNA, amino acid, protein, etc. In the past few years, they are embracing a new kind of data, gene order. We study the phylogeny reconstruction problem with maximum parsimony for both gene-order and gene-sequence data. Unlike other researchers who work on heuristic algorithms due to the exponential possible tree topologies, we focus on exact algorithms that give the optimal solution.

ISBN: 0496769217Subjects--Topical Terms:

626642
Computer Science.

High-performance algorithms for phylogeny reconstruction with maximum parsimony.
LDR:03042nmm 2200301 4500 001 1840337
005 20050721102959.5
008 130614s2004 eng d
020 $a 0496769217
035 $a (UnM)AAI3129663
035 $a AAI3129663
040 $a UnM $c UnM
100 1 $a Yan, Mi. $3 1928677
245 1 0 $a High-performance algorithms for phylogeny reconstruction with maximum parsimony.
300 $a 96 p.
500 $a Source: Dissertation Abstracts International, Volume: 65-04, Section: B, page: 1962.
500 $a Adviser: David A. Bader.
502 $a Thesis (Ph.D.)--The University of New Mexico, 2004.
520 $a Phylogeny usually represented by an unrooted binary tree shows the evolutionary history of a set of species. Phylogenies derived from molecular data may prove crucial in answering some fundamental open questions in molecular evolution, and phylogeny reconstruction is a key research problem in computational biology. Biologists now study genomic sequences: DNA, amino acid, protein, etc. In the past few years, they are embracing a new kind of data, gene order. We study the phylogeny reconstruction problem with maximum parsimony for both gene-order and gene-sequence data. Unlike other researchers who work on heuristic algorithms due to the exponential possible tree topologies, we focus on exact algorithms that give the optimal solution.
520 $a We adopt new data structures and new algorithms and developed GRAPPA, gene-order based phylogeny reconstruction software. GRAPPA is much faster than its peer BPAnalysis, which is very popular. Some techniques employed in GRAPPA include a fast linear time algorithm to compute the inversion distance between species represented by signed gene-order data and a set of efficient tree generators to enumerate trees. We use the branch and bound approach to prune search space to find the optimal trees for a set of species based on sequence. We put forward some techniques such as rearranging sites to use the property of parsimonious un-informative sites to compute the tree length faster. We also designed a fast new optimization algorithm that takes constant time to compute the length of new trees compatible with a partial tree. This algorithm can not only be used in the branch and bound search, but also can be used in heuristic search techniques like SPR and TBR. To take advantage of the computability of modern computers, we use a simple data structure and a simple but efficient mutual lock mechanism to access the shared data in a high-performance implementation we designed for symmetric multiprocessors (SMPs).
520 $a We demonstrate the power of these techniques through an extensive performance study based upon simulated evolution under a wide range of model conditions.
590 $a School code: 0142.
650 4 $a Computer Science. $3 626642
650 4 $a Biology, Genetics. $3 1017730
690 $a 0984
690 $a 0369
710 2 0 $a The University of New Mexico. $3 1018024
773 0 $t Dissertation Abstracts International $g 65-04B.
790 1 0 $a Bader, David A., $e advisor
790 $a 0142
791 $a Ph.D.
792 $a 2004
856 4 0 $u http://pqdd.sinica.edu.tw/twdaoapp/servlet/advanced?query=3129663