GRAPPA: Genome Rearrangements Analysis under Parsimony and other Phylogenetic Algorithms
Copyright (C) 2000-2004, The University of New Mexico and The University of Texas at Austin
This program is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation – using version 2 (June 1991) of the License or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of or a link to the GNU General Public License along with this program; you can also write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.
GRAPPA is available as a gzipped tar file containing all source files needed to compile an executable version. Documentation for this early release is minimal (there is a README file and some online help). GRAPPA changes quickly, so be sure to grab the latest release.
GRAPPA was featured in Access, the magazine of the NCSA/Alliance in Vol. 14 (1) (Spring 2001). It is discussed at some length in
- Moret, B.M.E., Wyman, S., Bader, D.A., Warnow, T., and Yan, M., “A new implementation and detailed study of breakpoint analysis,” Proc. 6th Pacific Symp. on Biocomputing (PSB 2001), Hawaii, World Scientific Pub. (2001), 583-594. PS
Its linear-time computation of inversion distance is presented in
- Bader, D.A., Moret, B.M.E., and Yan, M., ``A linear-time algorithm for computing inversion distances between signed permutations with an experimental study,'' Proc. 7th Workshop on Algorithms and Data Structures (WADS 01), Providence (2001), Lecture Notes in Computer Science 2125, 365-376, Springer Verlag. Journal version appears in J. Comput. Biol. 8, 5 (2001), 483-491. PDF
The improvements due to better bounding and new search ordering (the layered method) are discussed in
- Moret, B.M.E., Tang, J., Wang, L.S., and Warnow, T., “Steps toward accurate reconstruction of phylogenies from gene-order data,” to appear in J. Comput. Syst. Sci. (invited, special issue on computational biology), 2002. PS
while the improvements achieved through the use of true inversion medians are documented in
- Moret, B.M.E., Siepel, A.C., Tang, J., and Liu, T., “Inversion medians outperform breakpoint medians in phylogeny reconstruction from gene-order data,” Proc. 2nd Int’l Workshop on Algorithms in Bioinformatics (WABI'02), Rome (2002), to appear in Lecture Notes in Computer Science 2452, 2002. PS
which also contains references to the works of A. Caprara and of A. Siepel, whose codes for the computation of true inversion medians are included in this release. The latest release is
from October 1, 2004. Previous releases (1.6 and 1.03) are obsolete.
You may want to look at some test data.
Authors (original): David A. Bader Electrical and Computer Engineering Department University of New Mexico Albuquerque, NM 87131 +1.505.277.6724 email@example.com www.eece.unm.edu/~dbader Bernard M.E. Moret Department of Computer Science University of New Mexico Albuquerque, NM 87131 +1.505.277.5699 firstname.lastname@example.org www.cs.unm.edu/~moret Tandy Warnow Department of Computer Sciences University of Texas, Austin Austin, TX 78712 +1.512.471.9724 email@example.com www.cs.utexas.edu/users/tandy/ Stacia K Wyman Department of Computer Sciences University of Texas, Austin Austin, TX 78712 +1.512.232.7432 firstname.lastname@example.org www.cs.utexas.edu/users/stacia Mi Yan Electrical and Computer Engineering Department University of New Mexico Albuquerque, NM 87131 +1.505.277.6185 email@example.com www.ahpcc.unm.edu/~miyan/ Main contributors to version 1.6: Jijun Tang Department of Computer Science University of New Mexico Albuquerque, NM 87131 firstname.lastname@example.org Adam C. Siepel Department of Computer Science and Engineering University of California at Santa Cruz Santa Cruz, CA email@example.com Alberto Caprara DEIS Universitá di Bologna 40136 Bologna, Italy firstname.lastname@example.org Main contributor to version 2.0: Jijun Tang Department of Computer Science and Engineering University of South Carolina email@example.com Maintainers: Bernard M.E. Moret firstname.lastname@example.org and Jijun Tang email@example.com