Please try below script. It may be helpful.

begin paup;

log file=mp-log;

set autoclose=yes;

set maxtrees=100 increase=no;

set criterion=parsimony;

outgroup XXXXXX;

hsearch addseq=random nreps=100 multrees=yes hold=1 swap=tbr;

showtrees;

describetrees 1/plot=phylogram brlens=yes;

pscores ALL/tl=yes ci=yes ri=yes rc=yes hi=yes;

savetrees file=mp-all.tre root=yes brlens=yes;

bootstrap nreps=1000 keepall=yes/AddSeq=random nreps=100 savereps=yes;

savetrees file=mp-boot.tre from=1 to=1 savebootp=both maxdec=0 root=yes brlens=yes;

pscores ALL/tl=yes ci=yes ri=yes rc=yes hi=yes;

log stop;

end;

Dear Dr. Kateřina Rylková 

Please try to read following two web link, might be you can some ideas.

www.bioon.com/book/biology/bioinformatics/chapter-14.pdf

http://www.abc.net.au/news/2014-02-13/mcdonald-the-human-cost-of-drought-cant-be-counted/5257574

My advice would be to use TNT for parsimony analysis.  PAUP is notoriously slow and searches tree space relatively poorly compared to TNT.  

Download TNT here: http://www.cladistics.com/aboutTNT.html

I'd agree with Rob that TNT is a good piece of software to use for parsimony searches, especially in this situation. Just to clarify though, are you running a bootstrap analysis here. If so, have you already run your heuristic search? What was your search strategy here, and how long did it take to find your MPT?

I'd guess that you have a relatively flat tree space - meaning there are lots of trees of a similar length, thus when you do a bootstrap you flatten the landscape even more and end up searching through many millions of trees. TNT is certainly better in this situation, but if you are uncomfortable with it  there might be ways to improve your PAUP search strategy, or maybe restrict it (depending on your needs).

Could it be that your sequence is too variable? (Check out Vesna Hristova's 1st link)

Please try below script. It may be helpful.

begin paup;

log file=mp-log;

set autoclose=yes;

set maxtrees=100 increase=no;

set criterion=parsimony;

outgroup XXXXXX;

hsearch addseq=random nreps=100 multrees=yes hold=1 swap=tbr;

showtrees;

describetrees 1/plot=phylogram brlens=yes;

pscores ALL/tl=yes ci=yes ri=yes rc=yes hi=yes;

savetrees file=mp-all.tre root=yes brlens=yes;

bootstrap nreps=1000 keepall=yes/AddSeq=random nreps=100 savereps=yes;

savetrees file=mp-boot.tre from=1 to=1 savebootp=both maxdec=0 root=yes brlens=yes;

pscores ALL/tl=yes ci=yes ri=yes rc=yes hi=yes;

log stop;

end;

I think there is no any problem in your analysis. I had the same problem with PAUP. It was to slow to finish when you use MP analysis! I solved with a PC via 8 core CPU.

A quick fix is to set u a large maxtrees (5000) and don't change it.  Probably most of the tress differ just in some tip topology and don't affect the general tree topology. Your data is probably too variable but with small differences among sequences and so small topological differences produce lots of trees with the same length. If you are dealing with intraspecific data or close species data try instead a network.  

I'd have to say, Kateřina, you should not analyse you DNA sequence data using MP method at all. As you methoded, you data are very variable, it could expect that homoplacy will be prevalent. You can not approache the trure tree(s). Just switch to ML and Bayesian methods which are statistically robust for DNA data.

I agree with Chengmin Shi. Mp method is apply to closely-related species with more parsimony informative sites.

Dear Kateřina, 

As several colleagues mentioned above, I would give up of PAUP and focus on TNT, which is much faster and allows you to implement better algorithms for tree search in reasonable time. I would also suggest you to take a look at POY. This software can deal with the tree alignment problem; you may be interested. Take a look in the attached paper.

Best wishes

Thank you all for your advice and suggestions.