English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
 
 
DownloadE-Mail
 Local TagsRelease HistoryDetailsSummary
  An Improved Algorithm for the Macro-evolutionary Phylogeny Problem

Behzadi, B., & Vingron, M. (2006). An Improved Algorithm for the Macro-evolutionary Phylogeny Problem. In Combinatorial Pattern Matching (pp. 177-187). Berlin/Heidelberg: Springer.

Item is

 

show all hide all

Basic

show hide
Item Permalink: https://hdl.handle.net/11858/00-001M-0000-0010-84E8-7 Version Permalink: https://hdl.handle.net/11858/00-001M-0000-0010-84E9-5
Genre: Book Chapter

Files

show Files
hide Files
:
fulltext.pdf (Any fulltext), 420KB
 
File Permalink:
-
Name:
fulltext.pdf
Description:
-
OA-Status:
Visibility:
Restricted (Max Planck Institute for Molecular Genetics, MBMG; )
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
eDoc_access: MPG
License:
-

Locators

show

Creators

show
hide
 Creators:
Behzadi, Behshad1, Author
Vingron, Martin2, Author           
Affiliations:
1Max Planck Society, ou_persistent13              
2Gene regulation (Martin Vingron), Dept. of Computational Molecular Biology (Head: Martin Vingron), Max Planck Institute for Molecular Genetics, Max Planck Society, ou_1479639              

Content

show
hide
Free keywords: -
 Abstract: Macro-evolutionary processes (e.g., gene duplication and loss) have rarely been incorporated into gene phylogeny reconstruction methods. Durand et al. [5] have proposed a polynomial time dynamic programming algorithm to find the gene family tree that optimizes a macro-evolutionary criterion which is the weighted sum of the number of gene duplications and losses. The complexity of this algorithm is O(nm2) where n is the number of species and m is the maximum number of copies of the gene in a species. In this paper, we propose an improved algorithm with time complexity of O(nm) for solving this problem. We also show, that the problem can be solved in O(n) if unit costs are considered for both loss and duplication.

Details

show
hide
Language(s): eng - English
 Dates: 2006-01-01
 Publication Status: Issued
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Type: -
 Identifiers: eDoc: 309234
DOI: 10.1007/11780441
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Combinatorial Pattern Matching
Source Genre: Book
 Creator(s):
Lewenstein, Moshe, Author
Valiente, Gabriel, Author
Affiliations:
-
Publ. Info: Berlin/Heidelberg : Springer
Pages: 414 Volume / Issue: - Sequence Number: - Start / End Page: 177 - 187 Identifier: ISBN: 3-540-35455-7

Source 2

show
hide
Title: Lecture Notes in Computer Science
Source Genre: Series
 Creator(s):
Goos, Gerhard, Editor
Hartmanis, Juris, Editor
van Leeuwen, and Jan, Editor
Affiliations:
-
Publ. Info: -
Pages: - Volume / Issue: 4009/2006 Sequence Number: - Start / End Page: - Identifier: -