Identifying optimal incomplete phylogenetic data sets from sequence databases.
We introduce a new method for identifying optimal incomplete data sets from large sequence databases based on the graph theoretic concept of alpha-quasi-bicliques. The quasi-biclique method searches large sequence databases to identify useful phylogenetic data sets with a specified amount of missing data while maintaining the necessary amount of overlap among genes and taxa. The utility of the quasi-biclique method is demonstrated on large simulated sequence databases and on a data set of green plant sequences from GenBank. The quasi-biclique method greatly increases the taxon and gene sampling in the data sets while adding only a limited amount of missing data. Furthermore, under the conditions of the simulation, data sets with a limited amount of missing data often produce topologies nearly as accurate as those built from complete data sets. The quasi-biclique method will be an effective tool for exploiting sequence databases for phylogenetic information and also may help identify critical sequences needed to build large phylogenetic data sets.
Yan
Changhui
C
Department of Computer Science, Iowa State University, Ames, IA 50011, USA.
Burleigh
J Gordon
JG
Eulenstein
Oliver
O
D001483:Base Sequence / Q000235:genetics*; D002965:Classification / Q000379:methods*; D019295:Computational Biology; D003198:Computer Simulation; D003627:Data Interpretation, Statistical; D010802:Phylogeny