Send to

Choose Destination
See comment in PubMed Commons below
IEEE/ACM Trans Comput Biol Bioinform. 2010 Apr-Jun;7(2):288-98. doi: 10.1109/TCBB.2008.73.

Reassortment networks for investigating the evolution of segmented viruses.

Author information

  • 1Department of Biomedical Informatics, Ohio State University, 3190 Graves Hall, 333 W. 10th Ave. Columbus, OH 43210, USA.


Many viruses of interest, such as influenza A, have distinct segments in their genome. The evolution of these viruses involves mutation and reassortment, where segments are interchanged between viruses that coinfect a host. Phylogenetic trees can be constructed to investigate the mutation-driven evolution of individual viral segments. However, reassortment events among viral genomes are not well depicted in such bifurcating trees. We propose the concept of reassortment networks to analyze the evolution of segmented viruses. These are layered graphs in which the layers represent evolutionary stages such as a temporal series of seasons in which influenza viruses are isolated. Nodes represent viral isolates and reassortment events between pairs of isolates. Edges represent evolutionary steps, while weights on edges represent edit costs of reassortment and mutation events. Paths represent possible transformation series among viruses. The length of each path is the sum edit cost of the events required to transform one virus into another. In order to analyze tau stages of evolution of n viruses with segments of maximum length m, we first compute the pairwise distances between all corresponding segments of all viruses in O(m2n2) time using dynamic programming. The reassortment network, with O(taun2) nodes, is then constructed using these distances. The ancestors and descendents of a specific virus can be traced via shortest paths in this network, which can be found in O(taun3) time.

[PubMed - indexed for MEDLINE]
PubMed Commons home

PubMed Commons

How to join PubMed Commons

    Supplemental Content

    Full text links

    Icon for IEEE Engineering in Medicine and Biology Society
    Loading ...
    Support Center